在旅行商问题穿越边缘 [英] crossing edges in the travelling salesman problem

问题描述

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

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).

这篇关于在旅行商问题穿越边缘的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！