Решатель TSP без неравенства треугольника

Question

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

Например, я бы хотел, чтобы решатель вывел маршрут (0, 1, 2, 1, 4, 3) для графика (с единичными весами ребер) ниже:

0-1-2
| |
3-4

В этом конкретном случае я сказал конкорду, что ребро (2, 4) имело вес 1000, и конкорд быстро произвел тур (0, 1, 2, 4, 3) стоимостью 1004. Это явно не то, что я ищу.

В идеале, в Java должна быть какая-то простая (возможно, грубая сила) реализация, но все, что работает, действительно будет работать. Кто-нибудь может указать мне какой-нибудь код или мне действительно нужно самому реализовать это?

Редактировать: также важно, чтобы я получил точное решение, а не какое-то приближение.

Edit2: действительно, это не похоже на TSP. Я пытаюсь найти кратчайший закрытый проход, который посещает все вершины.

Answer 1

Ваша трудность не в неравенстве треугольника.Сложность связана с тем, что ожидаемое решение не является действительным TSP туром.

TSP ищет гамильтонов цикл ;то есть цикл, который посещает каждую вершину ровно один раз.Ваше решение, (0, 1, 2, 1, 4, 3), дважды посещает вершину 1.

Если это решение, которое вы ищете, то проблема, которую вы пытаетесь решить, это не проблема коммивояжера.