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

Question

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

Answer 1

这是 Travelling Salesman Problem其中每对点之间的距离是 |y2-y1|+|x2-x1| (称为直线距离或 Manhattan distance )。这是NP-hard这基本上意味着没有已知的有效解决方案。

Methods to solve it在维基百科上。

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