I can't understand FindShortestTour

A tour must return to the starting point; i.e. it is a cycle. Your proposed tours with lengths of 10 are not, and therefore could not have been found by FindShortestTour. Calculating the length explicitly shows that all three (the tour found by FindShortestTour and your proposed tours, when interpreted as returning to the beginning) have a length of 20, which is the minimum possible in this example:

pts = {{0, 1}, {5, 1}, {2, 1}, {10, 1}};
{len, tour} = FindShortestTour[pts];

ClearAll[tourEdgeLengths, tourLength];
tourEdgeLengths[pts_, tour_] := Norm /@ (pts[[tour]] - pts[[RotateLeft[tour]]]);
tourLength[pts_, tour_] := Total@tourEdgeLengths[pts, tour];

tourLength[pts, tour] (* FindShortestTour result is {1, 2, 4, 3} *)
(* -> 20 *)

tourLength[pts, {1, 3, 2, 4}]
(* -> 20 *)

tourLength[pts, {4, 2, 3, 1}]
(* -> 20 *)

Indeed, the methods "AllTours" and "IntegerLinearProgramming" are guaranteed to find the shortest tour, and these produce the same result as the default method.

The result obtained from FindShortestTour is a good example of the fact that, when seeking a traversal that is not a tour, in general one can not simply find the shortest cycle and then delete its longest edge to get the optimum solution. This would be the case for your tour {1, 3, 2, 4}:

tourEdgeLengths[pts, {1, 3, 2, 4}]
(* -> {2, 3, 5, 10} *)

i.e., deleting the last edge (4$\rightarrow$1, length 10) produces the shortest Hamiltonian path. But, when considering the equally good tour {1, 2, 4, 3},

tourEdgeLengths[pts, {1, 2, 4, 3}]
(* -> {5, 5, 8, 2} *)

we see that deleting the edge 4$\rightarrow$3 (length 8) leaves us with a non-optimal, length-12 traversal.

I can confirm that result (Linux, 64 bit). Indeed, a good example that shows how bad some (most) outputs of FindShortestTour are. I've made a few posts regarding the add-on package JVMTools already, for example here, so I'll just keep it with that link. JVMTools uses industrial-strength algorithms that produce optimal solutions for a few hundred nodes in a few seconds, and solutions that are only 1 - 2% above optimal for a few thousand nodes. All algorithms use concurrency to submit competing strategies and initial nodes (and then returns either all solutions or only the best, based on the user's choice), and also uses ant-colony / multi-agent optimization algorithms for outstanding quality and speed results.

Disclosure: I am the owner of Lauschke Consulting, which is the business that sells JVMTools commercially.

FindShortestTour is a complex function with multiple operation levels.

First of all there are two steps for FindShortestTour:

1. Tour generation
2. Tour improvement

FindShortestTour implements several tour generation methods. Space-filling curves is one for instance, another one is CCA (convex hull, cheapest insertion, angle selection).

All the methods for tour generation and tour improvement are not applied to your example, since there are not enough points. In your case FindShortestPath is clever enough and will switch to Minimize, implementing an elaborate Integer Linear Programming approach. (Caution! That _Mathematica) is using [N]Minimize internally might not be true at all. Let's suppose it does.)

Let's try to mimic what Mathematica is doing under the hood, when switching to Minimize.

• set up a variable which holds 1 or 0 if an edge from one point $i$ to another point $j$ is in the optimal tour
• minimize the total cost of the tour defined by the 1s

The problem with this approach is that the solution will be a collection of cycles.

Here the tour improvement step comes into play.

The first cycles after the first call to Minimize are killed. This is repeated as long as there is a cycle which involves all n points. Perfectly if this last cycle is a Hamilton cycle and the optimal tour (please see OleksandrR's answer).

The whole iterative process seems to be rather costly and it is indeed. That's why FindShortestTour switches to it only if the amount of points is smaller than a threshold.

Surprisingly it terminates quickly if the threshold is low enough.

The solution to your problem is {1, 3, 2, 4} and {1, 2, 4, 3} as well. They're all straight lines and since Euclid we know that lines are the shortest connections :). And as OleksandR already pointed out, that a tour is only a tour if you return to the starting point that's why the length is 20.