最佳优先搜索 TSP 在矩形上失败而在圆形上获胜，为什么？
Best First search TSP fails on rectangle and wins on circle why?
在旅行商问题中，这家伙需要去N个城市，他并不特别关心顺序，但他关心总距离。
假设城市在一个圆中，所有城市之间的距离相等，并位于两条平行线比沿线的城市距离更近
The authors claim that the Best-First Search algorithm works well on
the circle but not in the case of two parallel lines it will fail to
find the best solution because this strategy will make it zig-zag from
one line to the other while the perfect solution is a rectangle. In
this specific example, the winning strategy consists in trying the
2-best-first cities at every branch.
我真的不明白为什么会失败，为什么算法一开始就曲折？以及为什么在圆形的情况下它会正常运行。
Best-First搜索也会找到矩形的最佳解决方案。但是会花很长时间，因为在找到最优解之前会先找到很多不好的解。
绕一圈Best-First搜索最先找到的解就是最好的解。因为绕一圈是最好的办法。如果你总是取最近的其他点，你永远不会穿过圆的内部，这不是最优的。
在旅行商问题中，这家伙需要去N个城市，他并不特别关心顺序，但他关心总距离。
假设城市在一个圆中，所有城市之间的距离相等，并位于两条平行线比沿线的城市距离更近
The authors claim that the Best-First Search algorithm works well on the circle but not in the case of two parallel lines it will fail to find the best solution because this strategy will make it zig-zag from one line to the other while the perfect solution is a rectangle. In this specific example, the winning strategy consists in trying the 2-best-first cities at every branch.
我真的不明白为什么会失败，为什么算法一开始就曲折？以及为什么在圆形的情况下它会正常运行。
Best-First搜索也会找到矩形的最佳解决方案。但是会花很长时间，因为在找到最优解之前会先找到很多不好的解。
绕一圈Best-First搜索最先找到的解就是最好的解。因为绕一圈是最好的办法。如果你总是取最近的其他点，你永远不会穿过圆的内部，这不是最优的。