水平和垂直遍历点的算法
2D 平面上有 n 个点。机器人想要访问所有这些，但只能水平或垂直移动。它应该如何访问所有这些点才能使其覆盖的总距离最小？
There are n points in the 2D plane. A robot wants to visit all of them but can only move horizontally or vertically. How should it visit all of them so that the total distance it covers is minimal?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这是旅行推销员问题，其中每对点之间的距离为 |y2-y1| +|x2-x1| （称为直线距离或曼哈顿距离）。它是NP-hard，这基本上意味着没有已知的有效解决方案。
维基百科上的解决问题的方法。
最简单的算法是简单的强力搜索，您可以计算点的每个可能排列的距离并找到最小值。其运行时间为 O(n!)。这最多适用于大约 10 个点，但对于大量点来说，它很快就会变得太慢。
This is the Travelling Salesman Problem where the distance between each pair of points is |y2-y1|+|x2-x1| (called Rectilinear distance or Manhattan distance). It's NP-hard which basically means that there is no known efficient solution.
Methods to solve it on Wikipedia.
The simplest algorithm is a naive brute force search, where you calculate the distance for every possible permutation of the points and find the minimum. This has a running time of O(n!). This will work for up to about 10 points, but it will very quickly become too slow for larger numbers of points.