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

[A random solution to the traveling salesman problem]

This post describes the traveling salesman problem (TSP) and explains how the example program searches random solutions.

The Traveling Salesman Problem

In the traveling salesman problem (TSP), you have a number of locations. Your goal is to visit each of the locations and return to your starting point while minimizing the total distance covered.

If there are N locations, then there are N! possible orders in which you can visit the locations. The function N! grows so quickly that you can only examine every possible ordering for a small number of locations. For example, 10! = 3,628,800 so you can reasonably examine all of those possible orderings on a reasonably fast computer in a few minutes. However, 20! = 2,432,902,008,176,640,000. If your computer could examine 1 million orderings per second, it would take you more than 77,000 years to examine them all.

This example shows how you can examine a number of random orderings to try to find a good solution. You're unlikely to find the best possible solution unless the number of locations is small and the number of random solutions is large, but you can always find some solution. Random search isn't perfect but it's better than nothing.

Code

When you click Generate, the program generates the indicated number of random points. When you click Random, it examines the given number of random solutions. As it works, the program draws the ordering it is considering. The Delay slider lets you adjust the number of milliseconds between orderings.

After it finishes examining the desired number of orderings, the program redisplays the best solution that it found. For a large number of points (like 10) and a comparatively small number of random orderings (like 100), it's unlikely that the program will find the best possible solution and often you can see how to improve the solution.

Generating Points

When you click Generate, the following code executes.

def generate_click(self): # Start with no tour. self.best_tour = None self.best_length = math.inf # Pick random points. wid = self.canvas.winfo_width() hgt = self.canvas.winfo_height() MARGIN = 20 self.num_points = int(self.num_points_var.get()) self.points = [] for _ in range(self.num_points): x = random.randint(MARGIN, wid - MARGIN) y = random.randint(MARGIN, hgt - MARGIN) self.points.append((x, y)) # Find distances between all pairs of points. self.distances = make_distances(self.num_points, self.points) # Enable solver and output buttons. self.enable_solver_buttons() self.tour_number_var.set('') self.best_length_var.set('') self.elapsed_time_var.set('') self.num_calls_var.set('') self.draw()

This method initializes the best tour and its length so we can use them later. It then loops through the desired number of points, picks random coordinates, and saves the points as tuples in self.points. The code then calls the make_distances method to find the distances between every pair of points. The method finishes by handling some miscellaneous user interface tasks.

make_distances

The following code shows how the program finds the distances between each pair of points.

def make_distances(num_points, points): ''' Make a two-dimensional array giving distances between points where distances[i][j] gives the distance from points[i] to points[j]. ''' distances = [[0 for i in range(num_points)] for j in range(num_points)] for i in range(num_points): for j in range(num_points): distances[i][j] = math.dist(points[i], points[j]) return distances

This method first creates a two-dimensional array distances to hold the distances and then loops through the points. For each point, it loops through the points again. Within the inner loop, it finds the distance between the two looping variables' points and saves the result.

Note that the distance between points A and B is stored twice, once as distances[A][B] and once as distances[B][A]. For normal Euclidean distances, those values will be the same, but there are cases where the distances may be different. For example, if you're driving on a street network that contains one-way streets, you may not be able to use the same path from A to B as from B to A.

Also note that each point's distance to itself is also save as distances[A][A] and that value will be 0.

Getting Started

When you click Random, the program executes the following code.

def random_click(self): '''Solve by using random orderings of the points.''' print('Random: ', end='') self.solve(make_random_tour_generator)

This code simply calls self.solve passing it the make_random_tour_generator method. I'll describe that method later. For now, here's the solve method.

def solve(self, make_tour_generator): '''Solve by using the given generator.''' # Reset any previous tour. self.best_tour = None self.best_length = math.inf # Disable the solver buttons. self.disable_solver_buttons() self.best_length_var.set(f'{self.best_length:.0f}') self.elapsed_time_var.set('') self.num_calls_var.set('') # Make a tour generator. num_trials = int(self.num_trials_var.get()) self.tour_generator = make_tour_generator(self.num_points, self.distances, num_trials=num_trials) self.tour_number = 0 # Start generating tours. self.start_time = time.time() self.check_next_tour()

This code sets best_tour to None and best_length to infinity so the first complete tour found will replace best_tour. It performs some user interface tasks, gets the desired number of tours, and calls make_tour_generator to create the random tour generator. (Recall that random_click passed the make_random_tour_generator method in for this parameter so at this point make_tour_generator is make_random_tour_generator.)

The code saves the current time and calls check_next_tour to start finding tours.

check_next_tour

The check_next_tour method is where the fun really begins. It examines one tour and then uses after to schedule itself to run again to check the next tour until it runs out of tours to check. Here's the code.

def check_next_tour(self): global num_calls try: # Get the next tour. This throws # StopIteration if the generator is empty. test_length, test_tour = next(self.tour_generator) # Display the tour number. self.tour_number += 1 self.tour_number_var.set(f'{self.tour_number}') # Draw the test tour (if we're not going as fast as possible). if self.ms > 0: self.draw(test_tour) # See if this is an improvement. if test_length < self.best_length: # Save the improved tour. self.best_length = test_length self.best_tour = test_tour.copy() # Display the improved length. self.best_length_var.set(f'{self.best_length:.0f}') # Pause and repeat. self.window.after(self.ms, self.check_next_tour) except StopIteration: # We've finished the desired number of trials. stop_time = time.time() self.best_length_var.set(f'{self.best_length:.0f}') self.elapsed_time_var.set(f'{stop_time - self.start_time:.2f}') self.num_calls_var.set(f'{num_calls}') # Print results. print(f'Length: {self.best_length:>6.0f}, ' + \ f'Time: {stop_time - self.start_time:.2f}, ' + \ f'Calls: {num_calls:>6d}') # Re-enable the solver buttons. self.enable_solver_buttons() # Draw the best tour. self.draw(self.best_tour)

This code calls next on the generator to get its next solution and its length. It then increments and displays the tour number so you can see how many tours it has checked.

Next, if the desired delay self.ms between displays is not zero, the code calls self.draw to display the latest tour. If the delay is zero, the code doesn't display the tour so it can run as fast as possible.

Next, the code checks whether the new tour gives a lower total distance than the previous best tour and saves it if it does. It uses after to schedule check_next_tour to run again after the desired delay.

When the generator runs out of random tours, it throws the StopIteration exception and the except clause springs into action. The program displays the shortest tour length it found, the elapsed time, and the number of "calls" it made. You'll learn more about that shortly.

The code re-enables some buttons and then draws the best solution that it found. This time it does not call after so check_next_tour doesn't run again.

make_random_tour_generator

The make_random_tour_generator method is the heart of the random path algorithm. It generates and yields random tours. See the post Use the yield statement to generate primes in Python for an example that explains how the yield statement works.

Here's the code.

def make_random_tour_generator(num_points, distances, **kwargs): '''Return random tours.''' global num_calls num_calls = 1 # 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 tour and yield it. random.shuffle(tour) yield tour_length(num_points, tour, distances), tour

This method first sets the global variable num_calls to 1 to indicate that this method was called one time. This value isn't too interesting right now but will be more useful later when we're using algorithms that search the possible tours.

The code then gets the desired number of trials from the kwargs parameter and loops through the desired number of trials. For each, it uses random.shuffle to randomize the order of the points. It calls tour_length to get the tour's total length and then yields the length and tour.

That's all there is to it! The method repeatedly yields tours until it has yielded num_trials of them. The check_next_tour method uses next to get the next tour until make_random_tour_generator runs dry.

tour_length

Here's the tour_length method, which calculates the total length of a tour.

def tour_length(num_points, tour, distances): total_length = 0 for index in range(num_points): i = tour[index] j = tour[(index + 1) % num_points] total_length += distances[i][j] return total_length

This method loops through the tour's points. It calculates the distance between each point and the next one, using the modulus operator to wrap around to the first point when it reaches the end. It then returns the total distance.

Summary

I know this is a lot of pieces and it's easy to get confused, particularly because the progam is full of user interface code that does things like disable and re-enable buttons and draw the current tour. Here's the basic idea behind the random TSP algorithm:

Initialize best_length to infinity.
For a desired number of trials:
1. Generate a random tour.
2. If it's length is smaller than best_length, save the new tour and update best_length.

That's simple enough. Here's an outline of how the program does that.

When you click Generate:
1. Pick the desired number of random points.
2. Call make_distances to find the distances between all pairs of points.
When you click Random:
1. Call solve passing it the generator method make_exhaustive_tour_generator. (Later examples will pass different generator methods into solve so we can try different approaches to generating test solutions.)
2. The solve method does the following:
  1. Reset the best solution.
  2. Enable and disable buttons and whatnot.
  3. Call make_tour_generator to create the tour generator.
  4. Call check_next_tour to check the first tour.
3. The check_next_tour method does the following:
  1. Use next to get the generator's next tour.
  2. If the delay is greater than zero, display this tour.
  3. If this tour is an improvement, save it as the new best tour.
  4. Use after to run check_next_tour again after a delay.
  5. If the call to next throws the StopIteration exception, then we're done so re-enable buttons and stop.

I know it's a lot to digest. The indirect way the program uses after and a generator function makes things more complicated, but it lets us display tours as they are considered. It also lets us use different generators to try other approaches to solving the TSP later. The setup now is a bit complicated, but it makes it easy to install other generators later.

Download the example to experiment and see additional details. It's worth spending some time to understand this example so you'll be able to follow later examples more easily.