Solving a traveling salesman problem on a plane by a recursive greedy algorithm

In a previous publication , an algorithm for solving the traveling salesman problem on the plane by a recursive brute force was considered. The result was curious, but the final route contained obvious non-optimal sections. The proposed note describes an improved algorithm, which I called the "recursive greedy algorithm." I admit at once, the final route in comparison with the recursive brute force turns out better, on average, by 8%.

Once again we formulate the problem.
Given N nodes located on the plane. An input node (Bx) and output node (Out) are specified. You must discover the shortest path that encompasses all nodes, starting at the input node, ending at the output node, and passing through each node only once.

To synthesize a plan for solving a problem, we take 2 considerations as a basis.
1. The shortest path between two points on the plane lies in a straight line.
2. The most distant nodes introduce the greatest error in the total length of the route if these far nodes are not connected in the best way to the other nodes.

Based on these two considerations, we construct the algorithm in this way.
1. Connect the input and output nodes with a straight line. This final route from node “B” to node “Out” will obviously be the shortest.
2. However, in the task there are, unfortunately, other nodes that should also be included in the final route. Therefore, we will try to worsen this best shortest route in a minimal way and we will include the other nodes one by one, one after the other.
3. To do this, out of all the remaining nodes, we will select the interconnecting node to the original two nodes (since, due to our second consideration, this node introduces the maximum error) and include it in the shortest route found optimally - break the link between the I and O and connect In and Out through this third inter-focal node.
4. Next, we recursively find the inter-far node to the first three nodes and include it in the final route so that this inclusion will give a minimal increase in the length of the route. It is clear that when this fourth node is turned on, we will have a choice of two edges (for the third node there was no such choice). For the fifth node - a choice of three edges, and so on. Therefore, hereinafter, we will have to go through all the edges of the current route for each new inter-distant node and choose from them that edge, the gap of which will give a minimal increase in length (due to this “greedy” circumstance the algorithm got its name).
5. We will do the same with the remaining nodes.
')
The program and source codes on Object Pascal can be downloaded here .

Advantages of the algorithm:
1. Simplicity.
2. Speed. On a 2.67 GHz quad-core machine, 1000 nodes are calculated (on average) in 3 seconds.
2000 knots - in 27 seconds
3000 knots - in 87 seconds
4000 knots - in 207 seconds
The time gain is exponential, but for practical purposes this growth is rather slow.
3. In comparison with the previously proposed algorithm, the result is better by about 8%.
4. Minimum use of RAM.
5. The absence of any settings.
6. Minimum number of intersections without any intersection check.

The disadvantages , as usual, are the reverse side of the merits:
1. The lack of settings does not allow, if necessary, degrade the quality of the route by reducing the time to calculate it.
2. Intersections are extremely rare, but they still happen.
3. Exponential growth is still unclear how to slow down. It is possible, to go through not all edges, but only those closest to this node.