Я знаю, что это довольно частый вопрос (tsp в целом), но я был озадачен этим на некоторое время. Я ищу, чтобы найти минимальный путь гамильтониана, заданный набором координат x, y. Начальная и конечная точки совершенно произвольны, но они НЕ должны циклически повторяться, поэтому стандартная tsp отсутствует (хотя предположительно добавление фиктивной точки на расстоянии 0 во все другие узлы и последующее ее удаление позже, я понятия не имею, как бы я это сделал ).
Существует множество ссылок на математические статьи и тому подобное, обсуждающих алгоритмы для решения аналогичных задач, но я бы предпочел работать с кодом, а не со сложными уравнениями, и я действительно не хотел бы изобретать колесо.
Конечно, есть довольно простая реализация в основном языке java, c #, c ++, ruby, javascript, php и т. Д., Которая может решить версию моей проблемы на ~ 20 узлах.
Редактировать: Я также ищу как можно более точную, очевидно, она не может быть полностью точной, как 20! это много перестановок, но было бы идеально, если бы они были равны или лучше, чем то, что человек мог бы сделать за пару минут.
Edit2: Также, чтобы уточнить, я работаю со стандартными 2d координатами на невзвешенном графике. Расстояние A-> B == B-> A
Edit3: Чтобы устранить путаницу, вот визуальный пример с несколькими точками, чтобы показать, как tsp может быть неоптимальным (этот случай легко исправить, но с большим количеством узлов он может быть более экстремальным).
TSP минус самый длинный сегмент (красная линия)
Желаемый выход
