Traveling Salesman Problem: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 24: Line 24:
     for each j∈S, j≠1:
     for each j∈S, j≠1:
   
   
         A[S,j] = min { A[S-{j},k] + C<sub>kj</sub>
         A[S,j] = min { A[S-{j},k] + C<sub>kj</sub> }
                <sub>k∈S</sub>
                  k∈S
                <sub>k≠j</sub> 
                  k≠j
         n
         n
  return min { A[{1,2,3,...,n},j] + C<sub>j1</sub> }
  return min { A[{1,2,3,...,n},j] + C<sub>j1</sub> }

Revision as of 02:47, 27 November 2021

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 }
       j=1

Playground Implementation