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

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

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

0-1-2 
| | 
3-4

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

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

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

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

источник

2012-02-28 Dino

Вы уверены, что используете Concorde правильно? Он должен быть * точным * решателем для симметричной задачи TSP ... –

@ Li-aungYip: Concorde на самом деле дает оптимальное решение TSP. Проблема в том, что OP ожидает решение, которое не является действительным туром TSP. См. Мой ответ для деталей. – NPE

Я вижу. На самом деле, учитывая этот график, я не думаю, что есть * любой * другой закрытый цикл, который посещает все узлы. (ключевое слово: закрыто. 2-1-0-3-4 имеет вес 4 и посещает все узлы, но он не закрыт.) –

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

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

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

источник

2012-02-28 09:00:07 NPE

Спасибо, что указали это! Поэтому я предполагаю, что сначала должен вычислить матрицу расстояний между всеми вершинами в моем графе, а затем решить TSP. Это должно дать мне длину оптимального тура в моей сетке. Верный? – Dino

@ Duh: Честно говоря, я не вижу, как это поможет превратить вашу проблему в TSP. В любом случае, я думаю, что полезным первым шагом является выяснение того, что именно вы ищете (самый короткий цикл, который посещает каждую вершину * хотя бы один раз?) – NPE

Да, это именно то, что я ищу. И в этом случае перемещение задачи на полный график с точными расстояниями решает проблему: - Легко показать, что длины оптимальных решений равны - Легко ли построить тур по моему смыслу от оптимального Тур TSP в полном графике – Dino

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

ответ

Смежные вопросы