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: Use exhaustive search to solve the traveling salesman problem in Python

Before you go any further, review the previous post Use random search to solve the traveling salesman problem in Python. It explains the problem and the general approach used by this example. In a nutshell, the program uses a generator that uses the yield statement to produce orderings of the points. The program then compares them to find the shortest tour.

This example does the same thing except, when you click Exhaustive, it uses a new generator that examines every possible ordering of the points instead of a random selection.
Unfortunately, a random search doesn't always find the best possible tour. For example, in the picture on the right, a search of 1,000 random tours clearly didn't find the best possible result. We know it's not the shortest possible tour because it crosses itself and whenever a tour crosses itself, you can reorder it to improve the tour. (Look at the picture and see if you can figure out how.)

Code

def make_exhaustive_tour_generator(num_points, distances, **_): global num_calls num_calls = 0 # Prepare to call generate_exhaustive_tours. is_used = [False for i in range(num_points)] # Arbitrarily start at point 0. is_used[0] = True current_tour = [0] # Solve recursively. for length, tour in generate_exhaustive_tours( num_points, distances, is_used, current_tour): yield length, tour

The method initializes the is_used and current_tour lists as in the earlier post. It then calls the generate_exhaustive_tours method to do all of the real work. Because this method and that one are generators, this one must loop through the results returned by generate_exhaustive_tours and re-yield its results.

The following code shows the generate_exhaustive_tours method that exhaustively generates all of the possible tours.

def generate_exhaustive_tours(num_points, distances, is_used, current_tour): '''Generate all possible tours.''' global num_calls num_calls += 1 # See if we have a full tour. if len(current_tour) == num_points: # We have a full tour. Yield it. length = tour_length(num_points, current_tour, distances) yield length, current_tour else: # Pick the next point to add to the tour. for i in range(num_points): # Try to add points[i]. if not is_used[i]: # Add it. is_used[i] = True current_tour.append(i) # Recursively complete the tour. # Repeat until the nested generator runs dry. for length, tour in \ generate_exhaustive_tours( num_points, distances, is_used, current_tour): yield length, tour # Remove points[i] so we can use it again later. is_used[i] = False current_tour.pop()

The method first adds one to the global variable num_calls so we can keep track of the number of times this method is called. It then checks to see if we have a complete tour and, if so, the method yields it.

If we don't have a complete tour, the code loops through the points. If a point isn't in the current solution, the code adds it to the solution and recursively calls itself to fill on the rest of the tour. When the recursive call returns, the code removes the point from the tour so it can be used in future tours.

Because the recursive call is to a generator, this call loops through its returned results and re-yields them. The yield calls move up the call stack until they eventually pop out at the non-generator code that originally called make_exhaustive_tour_generator.

Summary

Download the example and see the two previous posts to experiment and to see additional details.