Traveling Salesman Problem: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
 
(15 intermediate revisions by the same user not shown)
Line 8: Line 8:


=Overview=
=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<sup>2</sup>2<sup>n</sup>).
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<sup>2</sup>2<sup>n</sup>).
 
=Algorithm=
=Algorithm=
<font size=-1>
Let A = 2D array, indexed by subsets S ⊆ {1,2,...,n} that contain 1, and destinations j ∈ {1,2,...,n}
<font color=teal># Initialize base case</font>
          │ 0 if S={1}
A[S,1] = │
          │ +∞ otherwise
for m = 2,3,4,...,n: <font color=teal># m = subproblem size</font>
  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] + C<sub>kj</sub> }
                k∈S
                k≠j
        n
return min { A[{1,2,3,...,n},j] + C<sub>j1</sub> } <font color=teal># min cost from 1 to j, visiting everybody once, </font>
        j=1                              <font color=teal># plus cost of final hop of the tour, that closes the loop</font>
==Playground Implementation==
==Playground Implementation==
{{External|https://github.com/ovidiuf/playground/blob/master/learning/stanford-algorithms-specialization/17-traveling-salesman-problem/src/main/java/playground/stanford/tsp/TravelingSalesmanProblem.java}}

Latest revision as of 02:57, 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 } # 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