Разделение в множествах эквивалентности

У меня есть простое дерево без слов T, Я должен найти путь с именем A и другой по имени B тот A а также B не имеют общей вершины. Цель состоит в том, чтобы максимизировать Len(A)*Len(B),

Я полагал, что эта проблема похожа на проблему с разделами, за исключением того, что в задаче о разделах у вас есть набор, но здесь у вас есть набор эквивалентности. Решение состоит в том, чтобы найти два непересекающихся пути, которые Len(A) ~ Len(B) ~ [n-1/2], Это исправление? Как я должен реализовать такой алгоритм?

0

Решение

Прежде всего. Я думаю, что вы смотрите на эту проблему неправильно. Насколько я понимаю, у вас есть график связанная проблема. Что вы делаете

  1. Постройте максимальное связующее дерево и найдите длину L.
  2. Теперь вы говорите, что эти два пути не могут иметь общих вершин, поэтому мы должны удалить ребро, чтобы архивировать это. Я полагаю, что каждое ребро, в котором находится ребро в вашем графике, равно 1. Итак, сумма двух путей A и B равна L-1 после того, как вы удалили ребро. Теперь проблема заключается в том, что вы должны удалить ребро так, чтобы произведение len (a) и len (b) было максимизировано. Вы делаете это, удаляя край в et ‘middel’ L. Почему, проблема в том же, что и в оптимизации области прямоугольника с фиксированным периметром. Короткое видео на YouTube на эту тему можно найти Вот.

Обратите внимание, что если ваш крайний вес не равен 1, то у вас есть более сложная проблема, потому что может существовать более одного максимального связующего дерева. Но вы можете разделить их по-разному, если это так, напишите мне в ответ, тогда я подумаю над решением, но у меня его нет под рукой.

Удачи.

0

Другие решения

Я думаю, что есть решение для динамического программирования, которое почти пригодно для отслеживания, если длина пути — это просто количество ссылок в путях (поэтому ссылки не имеют весов).

Работа с листьев вверх. В каждом узле необходимо отслеживать лучшую пару решений, ограниченную поддеревом с корнем в этом узле, и для каждого k лучшее решение с путем длины k, оканчивающимся в этом узле, и вторым путем максимальной длины где-то ниже этого узла и не касаясь пути.

Имея эту информацию для всех потомков узла, вы можете создать аналогичную информацию для этого узла и проложить себе путь до маршрута.

Вы можете видеть, что этот объем информации необходим, если вы рассматриваете дерево, которое на самом деле является просто линией узлов. Лучшее решение для линии узлов состоит в том, чтобы разделить ее на две части, поэтому, если вы разработали лучшее решение, только если длина строки 2n + 1, у вас не будет строительных блоков, необходимых для линии длиной 2n. + 3.

0

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector