Traveling Salesman Problem: Difference between revisions
Jump to navigation
Jump to search
| Line 4: | Line 4: | ||
=Internal= | =Internal= | ||
* [[NP Completeness#Subjects|NP Completeness]] | * [[NP Completeness#Subjects|NP Completeness]] | ||
* [[Dynamic_Programming#Overview|Dynamic Programming]] | |||
=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>). | ||
Revision as of 19:35, 26 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).