Traveling Salesman Problem: Difference between revisions
Jump to navigation
Jump to search
| Line 23: | Line 23: | ||
for each set S ⊆ {1,2,...,n} of size m that contains 1: | for each set S ⊆ {1,2,...,n} of size m that contains 1: | ||
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> | ||
k∈S | <sub>k∈S</sub> | ||
k≠j | <sub>k≠j</sub> | ||
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:46, 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 }
j=1