Traveling Salesman Problem: Difference between revisions
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
- 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
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