是否存在最优解有交叉边的旅行商问题？
节点位于 x-y 平面中，因此在这种情况下交叉意味着如果要绘制图形，连接四个独立节点的两条线段将相交。
最佳答案
如果闭合折线的两条边相交，则存在顶点相同但周长较小的折线。这是三角不等式的结果。因此，TSP 的解决方案必须是一个简单的多边形。参见 this article (图4)
关于algorithm - 旅行商问题中的交叉边，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2444125/