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?
+3
A:
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.
Mark Byers
2009-12-05 22:43:52
Are you sure the distance between pair of points is |y2-y1|+|x2-x1|? I'm quite sure its': sqrt((y2-y1)^2+(x2-x1)^2)
Sbm007
2009-12-05 22:47:24
That said, if you want a pretty good solution but not necessarily the absolute optimal one, that wikipedia page also has some good suggestions.
UncleO
2009-12-05 22:49:10
@Sbm007 Apparently, the robot can't move on a diagonal, so Mark is correct.
UncleO
2009-12-05 22:50:07
Ah of course. My bad!
Sbm007
2009-12-05 22:50:52
I voted for your answer, but I'd like to see a little better definition of NP-hard. There's much more to it than what you posted, obviously.
San Jacinto
2009-12-05 23:02:00
@San Jacinto: OK, I linked 'NP-hard' to Wikipedia. It's described there better than I could do myself.
Mark Byers
2009-12-05 23:05:25