path - 水平和垂直遍历点的算法

Question

二维平面上有 n 个点。机器人想要访问所有这些，但只能水平或垂直移动。它应该如何访问所有这些以使其覆盖的总距离最小？

Answer 1

这是旅行商问题，其中每对点之间的距离为 |y2-y1|+|x2-x1| （称为直线距离或曼哈顿距离）。它是NP 难的，这基本上意味着没有已知的有效解决方案。

在维基百科上解决它的方法。

最简单的算法是天真的蛮力搜索，您可以在其中计算每个可能的点排列的距离并找到最小值。这具有 O(n!) 的运行时间。这最多可以处理大约 10 个点，但对于大量点，它很快就会变得太慢。