旅行商问题中的交叉边

Question

存在一种旅行推销员问题，其中最优解的边缘会相交吗？

节点位于x-y平面中，因此在这种情况下交叉意味着如果你绘制出图形，则连接四个单独节点的两个线段会相交。

- bob

---

请定义交叉的边缘。 - Ben S

如果边交叉，则每个节点都与位置有关。本质上，这意味着交叉的边是一个节点，因此改变了最优解的视角。 - Pindatjuh

因为如果两架飞机的飞行路径相交，你总是可以在中途跳到另一架飞机上吗？ - Pete Kirkham

@Pete Kirkham，你的观点是什么？ - Pindatjuh

@Pindatjuh 机场/航班是一个图形的例子，可以输入到TSP求解器中，其中交叉边不会引入节点。 - Pete Kirkham

@bob 这个问题的答案完全取决于你没有提供的两个信息 - 你是否使用欧几里得度量，以及你是否可以将任何边的交叉看作一个节点。如果你有欧几里得度量但交叉处没有变化（例如在一组固定航班之间的平面航空公司），那么会有带有交叉的例子；如果你有其他度量方式，在交叉点处有隐式节点，则仍然会有例子；但如果你同时具有欧几里得度量和所有交叉点上的隐含节点，则lhf的推理适用。 - Pete Kirkham

Answer 1

如果一个闭合的折线中有两条边相交，那么可以构造一条有相同顶点但周长更小的折线，这是三角不等式的结果。因此，TSP的解必须是简单多边形。请参见该文章（图4）。

- lhf

---

问题：作为旅行推销员之旅的一部分，最后访问的城市是否需要连接回第一个访问的城市，并以这种方式使最后一条路径“交叉”/穿过多个先前的边缘？编辑：也许这取决于你如何绘制它？就像有一种方法可以将其绘制为不相交边缘的多边形。 - Jason

@Jason，我的回答重点是对于欧几里得TSP问题，解决方案永远不会交叉。 - lhf

以防万一文章移动：“销售和芯片”在AMS的专栏中 - Wolf

Answer 2

如果您考虑使用非欧几里得度量（例如L1曼哈顿距离），那么构建自相交的最短路径就会变得非常容易。

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

如果每个相邻的路口之间的距离都为1，那么所有的路径长度都是8，包括自交的路径1-->2-->3-->4-->1。

- user287792

---

然而，我相信这可以被翻译成在三维欧几里得空间中的旅行商问题，此时最优解（等同于这个问题的解），不会有交叉。我额外添加的关键是所有 NP 完全问题 - 包括曼哈顿距离 TSP 问题 - 可以“归约”到彼此之间。因此，解决曼哈顿 TSP 问题与解决欧几里得 TSP 问题没有区别...在欧几里得 TSP 中，没有最优解会有边交叉。 - Chris Hayes

Answer 3

如果从节点A到C的花费加上从B到D的花费大于从A到B和从C到D的花费，则可能出现交叉边。这可能是因为成本与节点之间的距离不成比例。

一个现实生活的例子可能是，从A到C有一笔奖金（例如，您可以走私一些违禁品），或者成本取决于先前的步骤（在交通灯处左转可能会浪费很多时间）。

- Ritsaert Hornstra

Answer 4

显然，任何连接的图形，在每个节点都有两条边的情况下，只有一种 TPS 解决方案，如果画出来有穿越，则符合您所述的标准。

如果您添加其他限制，例如，如果您正在模拟使用贸易风环游地球的情况，因此成本仅与空间位置有些相关，您可能会发现更复杂的情况是最优的。

- Pete Kirkham

---

“每个节点都有两条边的连通图”是一个圆圈，对吗？ - AVB