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