algorithm to traverse points horizontally and vertically

There ar开发者_StackOverflowe 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?

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.