由网友(满身坏脾气)分享简介：是否存在一个旅行商问题，其中的最佳解决方案具有跨的边缘？ Does there exist a travelling salesman problem where the optimal solution has edges that cross? 的节点是在xy平面，所以交叉在这种情况下意味着，如果你要绘制的曲线...

是否存在一个旅行商问题，其中的最佳解决方案具有跨的边缘？

Does there exist a travelling salesman problem where the optimal solution has edges that cross?

的节点是在xy平面，所以交叉在这种情况下意味着，如果你要绘制的曲线图中，连接四个独立的节点都相交的两条线段

The nodes are in an x-y plane, so crossing in this case means if you were to draw the graph, two line segments connecting four separate nodes would intersect.

推荐答案

如果在一个封闭的折线横两条边，再有就是用相同的顶点的折线，但较小的周长。这是三角不等式的结果。因此，一个解决方案，以对TSP必须是一个简单的多边形。见这篇文章（图4）。

If two edges in a closed polygonal line cross, then there is a polygonal line with the same vertices but with smaller perimeter. This is a consequence of the triangle inequality. So, a solution to the TSP must be a simple polygon. See this article (Figure 4).