This example uses an algorithm to find a number's prime factors. For other interesting algorithms, see my book Essential Algorithms, Second Edition. The book describes many fascinating algorithms in pseudocode with source code available for download in Python and C#.

Title: Understand the 2-opt algorithm for solving the traveling salesman problem

This is a fairly complicated algorithm so I'm going to cover it in two posts. In this post, I'll explain the 2-opt algorithm. In the next one, I'll show you the Python implementation.

The post Improve branch and bound to solve the traveling salesman problem in Python explains how to use an improved branch and bound algorithm to solve the traveling salesman problem (TSP). It's just one of many approaches to solving the TSP with various numbers of points. Exhaustive search gets you to about 12 or so points, the first branch and bound algorithm gets you to 15 or so points, and the revised version gets you up to around 20 points.

The performance of both branch and bound algorithms depends heavily on the specific points involved and their arrangement so you can probably solve larger problems sometimes, but at some point those algorithms just won't be fast enough. When the problem is large, you have to rely on heuristics to find a solution that's good but possibly not perfect.
Random search is fast for all problem sizes, but it's unlikely to find a good solution for a large problem. For example, the picture on the right shows the best solution the program found out of 1 million random trials. The problem isn't that it didn't check a lot of combinations. The problem is that there are a HUGE number of possible tours. In that test, the program checks 1 million tours but there are 9.332622e+157 possible. As a percentage, the program checked 1.07151e-150% of the possible tours.

The 2-opt heuristic was first suggested in the 1950s. The idea is to start with a random tour and then repeatedly try to improve it.

The original key observation was that a tour that crosses itself can be easily improved. For example, consider the tour shown in Figure 1. The B-E and C-F links cross each other, so we can make an improvement as shown in Figure 2. We can shorten the tour by swapping the positions of points C and E so the tour visits the nodes in the order B-C-D-E-F. The two dashed green arrows are shorter than the magenta curves (by the triangle inequality), so this shortens the tour.

 

Note that we must also reverse the section of the tour between points C and E. Figure 3 shows the original tour. The magenta arrow shows the tour's direction. The green arrow shows the orientation of the tour between points C and E.

Figure 4 shows the revised tour with arrows showing the tour's new flow.

 

Figure 5 shows the way the program can make the swap. First it breaks the tour into Piece 1, Piece 2, and Piece 3. It reverses Piece 2 and stiches them back together.

A first statement of the 2-opt algorithm might be:

1. Pick a random tour.
2. Repeat until you cannot find any improvements:
   1. Loop through the tour's segments. If two segments cross, swap the two points C and E.
   2. Loop through

Swapping whenever segments intersect improves the tour, but sometimes other swaps can also improve the tour. For example, consider Figure 6. Swapping points G and H gives the improved tour shown in Figure 7.

 

Here's the final version of 2-opt.

1. Pick a random test tour.
2. Repeat until you cannot find any improvements:
   1. For each point A:
      1. For each point B:
         1. Swap points A and B, reversing the piece of the tour between them.
         2. If the result is shorter than the current test tour, save it.
         3. If the result is not shorter than the current test tour, unswap A and B.

Rather than looking for places where the tour crosses itself, this algorithm just tries making every possible swap and it keeps the ones that improve the tour.

It is possible that the order in which the swaps are considered changes the final result. I can imagine cases where swapping points A and B prevents you from later swapping points B and C. (Or B and D. Or A and E, or whatever.)

It's also possible that you might need to swap more than two points at a time to improve a tour. All of this means 2-opt isn't guaranteed to find an optimal solution, although it seems to do pretty well.

The following pictures show the program finding 100-point tours. In the picture on the left, the program examined 1 million random tours to find a pretty bad solution. In the picture on the right, the program used 2-opt with only 100 random tours. The 2-opt algorithm took about twice as long (it had to try a lot of swaps), but it found a much better tour. Is that the best tour possible? It's hard to say but it looks pretty good.

 

That's how the algorithm works. Stay tuned for my next post which will show how the example program implements 2-opt in Python.