算法水平和垂直地遍歷點

Question

2D平面中有n個點。機器人想要訪問所有的人，但只能水平或垂直移動。它應該如何訪問它們，以便它覆蓋的總距離最小？

Answer 1

這是Travelling Salesman Problem其中每對點之間的距離爲| y2-y1 | + | x2-x1 | （稱爲直線距離或Manhattan distance）。這是NP-hard這基本上意味着沒有已知的有效解決方案。

Methods to solve it維基百科的文章。

最簡單的算法是一個天真的蠻力搜索，您可以計算每個可能的點排列的距離並找到最小值。這有一個運行時間O（n！）。這將工作達10分左右，但對於大量點數來說，它會很快變得太慢。