algorithm - 如果旅行推销员乘飞机旅行怎么办？

Question

使用贪婪策略通过眼睛解决二维点对点旅行商问题似乎很直观。然而，如果图形在地形上是准确的，例如，我们只能通过肉眼解决 TSP。如果 A 到 B 是 10，A 到 C 是 10，那么 B 到 C 不能是 1000。

当我们服从 2D 缩放时，贪心策略是否仍然不是最优的，即乘飞机旅行？下面我设法创建了一个地形准确的例子，其中贪婪策略确实是次优的:

从 S 开始:

• 贪心算法:S B C A S => 2.83 + 4 + 5 + 2.2 => 14.03
• 最优:S A B C S => 2.2 + 3 + 4 + 3.16 => 12.36

上面的例子有什么特别的地方是所有次优贪婪路线共有的吗？可以使用几何来最小化错误吗？

Answer 1

我打算将@Dukeling 的评论扩展为一个完整的答案，因为它似乎很好地解决了所提出的问题:

如果图的顶点与平面中的点关联并且边的权重等于点之间的距离，则该图称为欧几里德图。

在欧氏图上求解 TSP 并不比在一般图上更容易。