пересечение краев в проблеме коммивояжера
Там существует проблема коммивояжера, где оптимальное решение имеет края тот крест?
Узлы находятся в x-y плоскости, таким образом пересекаясь в этом средстве случая, если бы необходимо было потянуть график, то два линейных сегмента, соединяющие четыре отдельных узла, пересеклись бы.
4 ответа
Если два ребра замкнутой ломаной пересекаются, значит, есть ломаная с такими же вершинами, но с меньшим периметром. Это следствие неравенства треугольника. Итак, решение TSP должно быть простым многоугольником. См. эту статью (рисунок 4).
Вы можете получить пересечение ребер, если стоимость перехода от узла A-> C плюс стоимость B-> D> стоимость A-> B и C- > D. Вы можете получить это, когда стоимость не зависит от расстояния между узлами.
Пример из реальной жизни может заключаться в том, что переход от пункта A к пункту C дает бонус (например, вы можете провезти контрабанду контрабандой) или стоимость зависит от предыдущих шагов (по Тьюрингу слева светофор может стоить вам много время).
Тривиально, любой связный граф, в котором каждый узел имеет два ребра, имеет только одно решение TPS, и если он нарисован с пересечениями, он будет соответствовать указанным вами критериям.
Если вы поставите другие ограничения, например, если бы вы моделировали кругосветное путешествие с использованием пассата, так что затраты лишь частично связаны с положением в космосе, вы можете найти более сложный случай, когда пересечение является оптимальным.
Если рассматривать неевклидову метрику, такую как L1 (расстояние до Манхэттена), то довольно легко построить кратчайшие туры, которые самопересекаются.
+--3--+
| | |
| | |
2--+--1
| | |
| | |
+--4--+
Если каждая соседняя пара пересечений находится на расстоянии 1, то все туры имеют длину 8, включая самопересекающийся, который идет 1 --> 2 --> 3 --> 4 --> 1.