Algorithms For Dummies

  Relying on Dynamic Programming 

     315

the problem efficiently. Therefore, when solving TSP for five cities, the algorithm 

first  considers  solutions  involving  two  cities,  then  three  cities,  then  four,  and 

finally five (sets have dimensions 1 to n). Here are the steps the algorithm uses:

1. 

Initialize a table to track the distances from city 0 to all other cities. These sets 

contain only the initial city and a destination city because they represent the 

initial step.

2. 

Consider every possible set size, from two to the number of tour cities. This is a 

first iteration, the outer loop.

3. 

Inside the outer loop, for each set size, consider every possible combination of 

cities of that size, not containing the initial city. This is an inner iteration.

4. 

Inside the inner iteration (Step 3), for every available combination, consider 

each city inside the combination as the ending city. This is another inner 

iteration.

5. 

Inside the inner iteration (Step 4), given a different destination city, determine 

the shortest path connecting the cities in the set from the city that starts the 

tour (city 0). In finding the shortest path, use any useful, previously stored 

information, thus applying dynamic programming. This step saves computa-

tions and provides the rationale for working by growing subsets of cities. 

Reusing previously solved subproblems, you find the shorter tours by adding 

to a previous shortest path the distance necessary to reach the destination city. 

Given a certain set of cities, a specific initial city, and a specific destination city, 

the algorithm stores the best path and its length.

6. 

When all the iterations end, you have as many different shortest solutions as 

n-1

 cities, with each solution covering all the cities but ending at a different 

city. Add a closing point, the city 0, to each one to conclude the tour.

7. 

Determine the shortest solution and output it as the result.

The Python implementation of this algorithm isn’t very simple because it involves 

some iterations and manipulating sets. It’s an exhaustive search reinforced by 

dynamic programming and relies on an iterative approach with subsets of cities 

and with candidates to add to them. The following commented Python example 

explores how this solution works. You can use it to calculate customized tours 

(possibly using cities in your region or county as entries in the distance matrix). 

The script uses advanced commands such as 

frozenset

 (a command that makes 

a set usable as a dictionary key) and operators for sets in order to achieve the 

solution.

from itertools import combinations

memo = {(frozenset([0, idx

+1]), idx+1): (dist, [0,idx+1])

---

316