пересечение ребер в задаче коммивояжера

Question

Существует ли проблема коммивояжера, когда оптимальное решение имеет пересекающиеся ребра?

Узлы находятся в плоскости x-y, поэтому пересечение в этом случае означает, что если бы вы рисовали график, два отрезка, соединяющих четыре отдельных узла, пересекались бы.

Answer 1

Если два ребра в замкнутой многоугольной линии пересекаются, то существует многоугольная линия с такими же вершинами, но с меньшим периметром. Это является следствием неравенства треугольника. Таким образом, решение TSP должно быть простым многоугольником. См. эту статью (рисунок 4).

Answer 2

Если вы рассматриваете неевклидову метрику, такую ​​как L1 (расстояние до Манхэттена), то довольно просто построить кратчайшие туры, которые самопересекаются.

+--3--+
|  |  |
|  |  |
2--+--1
|  |  |
|  |  |
+--4--+

Если каждая соседняя пара пересечений находится на расстоянии 1, то все маршруты имеют длину 8, включая самопересекающуюся, которая проходит 1 -> 2 -> 3 -> 4 -> 1.

Answer 3

Вы можете получить пересекающиеся ребра, если стоимость перехода от узла A-> C плюс стоимость B-> D> стоимость A-> B и C-> D. Вы можете получить это, когда стоимость не соответствует расстоянию между узлами.

Примером из реальной жизни может быть бонус от перехода от А к С (например, вы можете переправить контрабанду) или стоимость зависит от предыдущих шагов (оставление светофора может стоить вам много время).

Answer 4

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

Если вы наложите другие ограничения, например, если вы моделируете путешествие вокруг света с использованием пассатов, поэтому затраты лишь в некоторой степени связаны с положением в пространстве, вы можете найти более сложный случай, когда пересечение является оптимальным.