如果旅行推销员乘飞机旅行怎么办？
What if the travelling salesman travelled by plane?
使用贪心策略通过眼睛解决二维点对点旅行商问题似乎很直观。然而，如果图形在地形上是准确的，例如，我们只能通过肉眼解决 TSP。如果 A 到 B 是 10，A 到 C 是 10 那么 B 到 C 不能是 1000。
当我们服从二维缩放，即乘飞机旅行时，贪心策略是否仍然不是最优的？下面我设法创建了一个地形准确的例子，其中贪心策略确实是次优的：
从 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
上面的例子有什么特别之处是所有次优贪婪路线共有的吗？可以使用几何来最小化错误吗？
我打算将@Dukeling 的评论扩展为一个完整的答案，因为它似乎很好地解决了提出的问题：
如果图的顶点与平面中的点关联并且边的权重等于点之间的距离，则图称为欧几里德图。
在欧氏图上求解 TSP 并不比在一般图上更容易。
使用贪心策略通过眼睛解决二维点对点旅行商问题似乎很直观。然而，如果图形在地形上是准确的，例如，我们只能通过肉眼解决 TSP。如果 A 到 B 是 10，A 到 C 是 10 那么 B 到 C 不能是 1000。
当我们服从二维缩放，即乘飞机旅行时，贪心策略是否仍然不是最优的？下面我设法创建了一个地形准确的例子，其中贪心策略确实是次优的：
从 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
上面的例子有什么特别之处是所有次优贪婪路线共有的吗？可以使用几何来最小化错误吗？
我打算将@Dukeling 的评论扩展为一个完整的答案，因为它似乎很好地解决了提出的问题：
如果图的顶点与平面中的点关联并且边的权重等于点之间的距离，则图称为欧几里德图。
在欧氏图上求解 TSP 并不比在一般图上更容易。