Использование решателя коммивояжера для определения гамильтонова пути

Question

Это для проекта, в котором меня попросили реализовать эвристику для задачи оптимизации коммивояжера, а также для задачи принятия решения по гамильтоновому пути или циклу.Мне не нужна помощь с самой реализацией, но у меня есть вопрос о том, в каком направлении я иду.

У меня уже есть эвристика TSP, основанная на генетическом алгоритме:он предполагает полный граф, начинается с набора случайных решений в качестве совокупности и работает над улучшением совокупности в течение ряда поколений.Могу ли я также использовать его для решения гамильтоновых задач о пути или цикле?Вместо оптимизации для получения кратчайшего пути я просто хочу проверить, существует ли путь.

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

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

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

Answer 1

Не знаю, получили ли вы когда-нибудь ответ на этот вопрос.Простой трюк заключается в том, чтобы добавить одну фиктивную точку, имеющую нулевое расстояние ко всем остальным точкам.Решите задачу TSP и избавьтесь от фиктивной точки — останется гамильтонов путь.Простой !

Answer 2

Обе задачи являются NP-полными, поэтому по определению вы можете преобразовать входные данные и использовать один и тот же алгоритм ;-)

Но основная идея должна работать.Конечно, вам может потребоваться изменить создание новых путей и критерии успеха.

РЕДАКТИРОВАТЬ:КСТАТИ:Существует предложение для рандомизированного алгоритма:http://en.wikipedia.org/wiki/Hamiltonian_path_problem