Traveling Salesman Problem

External

• https://www.coursera.org/learn/algorithms-npcomplete/lecture/49MkW/the-traveling-salesman-problem
• https://www.coursera.org/learn/algorithms-npcomplete/lecture/uVABz/a-dynamic-programming-algorithm-for-tsp

Internal

• NP Completeness
• Dynamic Programming
• Bellman-Ford Shortest-Path Algorithm

Overview

The input is a complete undirected graph with non-negative edge costs. The output is a minimum cost tour (permutation of the vertices, a cycle that visits every vertex exactly once that minimize the sum of the edges). The brute force search running time is O(n!). The dynamic programming approach described here has a running time of O(n²2ⁿ).

Algorithm

Let A = 2D array, indexed by subsets S ⊆ {1,2,...,n} that contain 1, and destinations j ∈ {1,2,...,n}

# Initialize base case

         │ 0 if S={1}
A[S,1] = │ 
         │ +∞ otherwise 

for m = 2,3,4,...,n: # m = subproblem size
  for each set S ⊆ {1,2,...,n} of size m that contains 1:
    for each j∈S, j≠1:

       A[S,j] = min { A[S-{j},k] + Ckj }
                k∈S
                k≠j
        n
return min { A[{1,2,3,...,n},j] + Cj1 } # min cost from 1 to j, visiting everybody once, 
       j=1                              # plus cost of final hop of the tour, that closes the loop

Playground Implementation

https://github.com/ovidiuf/playground/blob/master/learning/stanford-algorithms-specialization/17-traveling-salesman-problem/src/main/java/playground/stanford/tsp/TravelingSalesmanProblem.java