Полиномиальное путешествие Путешественник с использованием дерева [Динамическое программирование]

Question

Если у нас есть N городов, где каждый город является лишь листом бинарного дерева, можно ли предложить динамическое программирующее решение, которое является полиномиальным временем? Я пытаюсь найти минимальное расстояние между всеми городами с ограничением только того, чтобы в первую очередь путешествовать по глубине. Мой подход - начать снизу вверх и рассчитать оптимальный путь для путешествий для каждого предка самых глубоких внутренних узлов. Таким образом, будет 4 города, которые будут оцениваться во время каждой из этих операций с помощью некоторой функции расстояния. Расстояние (x, y) = Расстояние (y, x). Если на каждой операции есть 4 города, у нас будет 8 возможных решений. Все остальные внутренние узлы приведут к суммированию нижних узлов. Корень будет в основном суммированием его детей. Неужели я направился в неправильном направлении или что?

Answer 1

Я предполагаю, что вы пытаетесь решить TSP на графике, который является деревом. Академическая версия этой проблемы, по-видимому, заключается в том, чтобы разрешить TSP на графиках «ограниченной тройной ширины», что, вероятно, является хорошим поисковым термином. http://www.cs.princeton.edu/~zdvir/apx11slides/erik-scribe.pdf содержит ссылку: «Фредерик Дорн, Федор Васильевич Фомин и Димитриос М. Тиликос. Каталонские структуры и динамическое программирование на графиках H-minor-free. В SODA '08: Материалы 19-го года Ежегодный симпозиум ACM-SIAM по Дискретные алгоритмы, стр. 631 {640. SIAM, 2008. ", к документу, который, как я подозреваю, более интересен математикам, чем программистам.

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

Возможно, неэффективный, но полиномиальный подход к динамическому программированию должен вычислять на каждом внутреннем узле для каждой пары городов внутри этого внутреннего узла стоимость лучшей поездки из города А в город Б, посещая все другие города под этим узлом (или маркер, который говорит «города на той же стороне - не делайте этого»). Вы можете это сделать для каждого внутреннего узла, используя информацию, вычисленную из своих детей, и на самом верху просто рассмотрите все лучшие предлагаемые маршруты и стоимость оставшейся ссылки, которая заставляет тур выработать кратчайший тур.