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: Improve branch and bound to solve the traveling salesman problem in Python

The post Use branch and bound to solve the traveling salesman problem in Python explains how to use branch and bound to solve the traveling salesman problem (TSP). The idea is to keep track of the length of the best tour found so far. When you add a new point to the test tour, you calculate the minimum length the tour could possibly have. If that minimum is greater than the best length found so far, you can ignore the current partial test tour and all of the tours that start with it.

To estimate the shortest possible length for the test tour, the program's best_possible_length function adds up the lengths of the shortest distances to the points that are not yet in the tour.

That works but we can eliminate more searching if we can get a more accurate estimate for the test tour's shortest possible length. We can do that if we think a bit more about how points are added to the test tour.

First, we only add new points at the end of the test tour, so a point A that is still unused will be reached either (1) from another unused point B or (2) from the last point in the current test tour. The previous version of best_possible_length looks at the shortest distance to point A. In the first change, we only consider (1) distances from other unused points to point A and (2) the distance from the last point in the current tour to point A.

We can make a second change if we remember that a complete TSP tour must visit every point and then return to the starting point. The previous version of branch and bound adds up the shortest distances to the new points but doesn't add a distance for the return to the starting point. We don't know exactly how far it will be because we don't know which point will be last in the tour, but we can use the smallest distance from any unused point to the starting point.

Code

def best_possible_length2(num_points, current_tour, distances, is_used): '''Return the best possible tour length starting from the current tour.''' # If this is a complete tour, return 0 so generate_b_and_b2_tours does it. if len(current_tour) == num_points: return 0 # This will be the shortest distance form # any unused point back to the start. best_return_distance = math.inf # The index of the last point in the current tour. last_point = current_tour[-1] # Loop through the points. total_length = 0 for i in range(num_points): # If point i is unused... if not is_used[i]: # ...find smallest distance into point i. length_to_i = math.inf for j in range(num_points): # Don't count i --> i (which has distance 0). if j == i: continue # Only count it if j is also unused or # j is the last point in the current tour. if j != last_point and is_used[j]: continue # See if this is a shorter distance. if distances[j][i] < length_to_i: length_to_i = distances[j][i] total_length += length_to_i # See if this point gives a shorter return. if distances[i][0] < best_return_distance: best_return_distance = distances[i][0] return total_length + best_return_distance

Summary

So how much difference does it make? The following table shows the number of function calls and the times used by exhaustive search, the original version of branch and bound, and the new version.

The improved version of branch and bound is always faster than the first version, which in turn is always faster than exhaustive search. The exact required by both versions of branch and bound vary depending on the points and their arrangement so they aren't consistent. You can see a particularly obvious example in the tests that used 19 and 20 points.

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