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: Implement the 2-opt algorithm for solving the traveling salesman problem in Python

[A solution to the traveling salesman problem found by 2-opt]

The previous post Understand the 2-opt algorithm for solving the traveling salesman problem explained how the 2-opt algorithm works. This post describes a Python implementation.

make_two_opt_tour_generator

The following make_two_opt_tour_generator starts the process.

def make_two_opt_tour_generator(num_points, distances, **kwargs): '''Return random tours improved by 2-opt.''' global num_calls num_calls = 0 # Make a list holding the point indices in order so we can shuffle it. tour = list(range(num_points)) # Perform the trials. num_trials = kwargs['num_trials'] for _ in range(num_trials): # Pick a random solution. random.shuffle(tour) # Use 2-opt to try to improve it. for improved_length, improved_tour in two_opt(num_points, tour, distances): yield improved_length, improved_tour

This part of the program is similar to a random search. It sets the global num_calls variable to zero and creates a tour list holding the point indices. Then, for the desired number of trials, it shuffles the tour list just as if it were generating a random tour. The only difference is that the program then calls two_opt to improve the random tour.

Because the two_opt method is a generator function, the make_two_opt_tour_generator method loops through the returned results and re-yields them.

The following two_opt method uses the 2-opt algorithm to try to improve a tour.

def two_opt(num_points, tour, distances): '''Use 2-opt to try to improve this tour. Return the best result.''' global num_calls # Keep track of the best tour. best_tour = tour.copy() # Repeat until we can find no more improvements. had_improvement = True while had_improvement: # Assume we won't hvae an improvement this time. had_improvement = False # Get the current tour's length. best_length = tour_length(num_points, best_tour, distances) # Loop through all pairs of points. # count = 0 # Print the count whenever we improve this tour. for i in range(num_points): for j in range(i + 1, num_points): num_calls += 1 # Swap points i and j. piece1 = best_tour[:i] # Points before point i piece2 = best_tour[i:j+1] # Points i through j inclusive piece3 = best_tour[j+1:] # Points after point j test_tour = piece1 + list(reversed(piece2)) + piece3 test_length = tour_length(num_points, test_tour, distances) # Yield the test solution. yield test_length, test_tour # See if this was an improvement. if test_length < best_length: best_length = test_length best_tour = test_tour.copy() had_improvement = True

This method makes a copy of the initial tour. As it works, it keeps a copy of the current best tour so it can undo changes that don't help.

The code then enters a loop that continues as long as we find an improvement. Within the loop, the program loops through all pairs of points. For each pair, the code uses the technique described in the previous post to swap the points. It divides the tour into three pieces, reverses the middle piece, and stitches the pieces together to form the new tour.

The method also yields the test tour so the main program can display it if you're drawing test tours. If you look closely, you may be able to see that groups of test tours are small modifications on an originally selected random tour. (You may need to use a large delay and work with many points.)

If the revised tour is an improvement over the current best your, the code saves it and sets had_improvement to True so we know to continue the while loop.

That's all there is to it. The real challenge is in understanding the algorithm and how to properly split the tour into three pieces.

Summary

For big traveling salesman problems (TSPs), exhaustive search and branch and bound aren't fast enough. If you have more than a couple dozen points, those approaches will take far too long to be useful. In that case, you need to turn to heuristics that produce a usable although probably not optimal solution. One such heuristic is the 2-opt algorithm.

In general, you probably can't determine whether a 2-opt result is optimal. One piece of evidence that these are reasonable tours is that they often resemble space-filling curves, which themselves provide reasonably good solutions to the TSP. In fact, one manual heuristic for the TSP is to place a Hilbert or Sierpinski curve on top of a map and then visit the points in the order in which the curve visits them. For more on Hilbert and Sierpinski curves, see my posts:

Download the example to experiment and see additional details.