Поиск гамильтонова пути против гамильтоновой схемы в полном неориентированном взвешенном графе

Question

У меня есть полный граф (матрица) с весами. Я построил решение для нахождения минимальной гамильтоновой схемы на этом графике (проблема с продавцом) с использованием ветвей и границ. Я теперь застрял в поиске лучшего пути гамильтониана с заданными начальными и конечными узлами. Без заданных начальных и конечных узлов лучшим решением будет гамильтонова схема - самый длинный край в цепи.

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

Answer 1

Данный начальный узел и конечный узел эквивалентны ограничению, что направленное ребро между конечным узлом и стартовым узлом должно быть частью тура TSP.

Таким образом, вы можете просто изменить свою матрицу смежности:

• набор всех исходящих ребра от желаемого конечного узла к бесконечной массе, за исключением края до начального узла
• набора всех входящих ребра к желаемой начальной от узла к бесконечному весу, за исключением края от конечного узла
• установить границу от стартового узла до конечного узла до бесконечного веса (чтобы убедиться, что вы не получите обратное решение, которое может отличаться, если ваше смежность матрица не симметрична)

Это очень похоже на метод ветвления, используемый вашей реализацией.

Answer 2

Добавьте большую константу к весу каждого края, кроме одного между заданным начальным и конечным узлами, который должен быть установлен на ноль. Константу можно выбрать как N*maxweight где N - число вершин, а maxweight - максимальный вес края. Это гарантирует, что данное ребро будет включено в схему.