Traveling Salesman Problem

From NovaOrdis Knowledge Base
Revision as of 02:57, 27 November 2021 by Ovidiu (talk | contribs) (→‎Playground Implementation)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

External

Internal

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(n22n).

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