Traveling Salesman Problem: Difference between revisions
Jump to navigation
Jump to search
| 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= | ||
==Playground Implementation== | ==Playground Implementation== | ||
Revision as of 19:52, 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).