Dynamic Programming in Python: Optimizing Programs for Efficiency/

...

/

Solution Review: The Traveling Salesman Problem

Solution Review: The Traveling Salesman Problem

In this lesson, we will review the solution to the famous traveling salesman problem.

We'll cover the following...

Solution 1: Simple recursion #

Press + to interact
import numpy as np
def TSPrecursive(distances, check, index, start):
  minimum = np.inf
  for i in range(len(distances)):
    if i != index and i != start and i not in check:
      check[i] = 1
      minimum = min(minimum, distances[index][i]+TSPrecursive(distances, check, i, start))
      del check[i]
  if minimum == np.inf:
    return distances[index][start]
  return minimum
def TSP(distances):
  check = {}
  minimum = np.inf
  for i in range(len(distances)):
    minimum = min(minimum, TSPrecursive(distances, check, i, i))
  return minimum
print(TSP([
      [0, 10, 20],
      [12, 0, 10],
      [19, 11, 0],
]))

Explanation

Let’s see what is going on here. In our main TSP function, we simply call the helper function TSPrecursive with different starting points. The starting point can play a huge role in finding the path with the minimum distance, that’s why we check with every option for the starting point and then take the min. In the helper function TSPrecursive, the idea is very similar. We exhaust every option for the next city we have and then pick the option that results in the minimum distance. We keep track of visited cities by keeping a dictionary check. The base case in this algorithm is when we have visited every city, in this case, the for loop from lines 5-9 won’t be triggered and thus the minimum would still be infinity. Thus, we will know we have reached the last city and now we can only go to the start city.

Here is a high-level dry run of this algorithm.

Time complexity

The time complexity of this algorithm, as evident from the above visualization, is O(n!). We are doing nothing but looking for all possible permutations of the cities, and the time complexity is in order of factorial.

Moreover, since we are keeping the check dictionary to keep track of visited cities, our algorithm has a space complexity of O(n).

Solution 2: Top-down dynamic programming

Let’s see how this problem satisfies both pre-requisites of using dynamic programming

Optimal substructure

This problem can be best explained using some concepts of set theory. As the order in which cities are visited is not important as long as all the cities are visited, unordered sets are a perfect fit for the problem. To construct a set of size nn, or to find an optimal answer to the problem of nn cities, we can explore which subproblems of size n−1n-1 leads to the optimal solution. Thus, if we have optimal answers to all the subproblems of size n−1n-1, we can construct an optimal answer to the main problem of nn.

Overlapping subproblems

Since we are finding permutations, we should expect to find a number of repetitions in the calculation of these permutations. Let’s revisit the above visualization to find the overlapping subproblems.

Press + to interact
import numpy as np
def TSPrecursive(distances, check, index, end, memo):
  keys = tuple(sorted(check.keys()))
  if (keys, index) in memo:
    return memo[(keys, index)]
  minimum = np.inf
  for i in range(len(distances)):
    if i != index and i != end and i not in check:
      check[i] = 1
      minimum = min(minimum, distances[index][i]+TSPrecursive(distances, check, i, end, memo))
      del check[i]
  if minimum == np.inf:
    return distances[index][end]
  memo[(keys, index)] = minimum
  return memo[(keys, index)]
def TSP(distances):
  check = {}
  minimum = np.inf
  for i in range(len(distances)):
    minimum = min(minimum, TSPrecursive(distances, check, i, i, {}))
  return minimum
print(TSP([
      [0, 10, 20],
      [12, 0, 10],
      [19, 11, 0],
]))

Explanation

The important detail in this solution is what we are using for memorization. Let’s rethink this in the context of the problem. How do we define a subproblem? For a problem of nn cities, we need the optimal solution to all the problems of size n−1n-1. If we had three cities, a,b,ca,b,c then the subproblems of size 22 ...