Traveling Salesman Problem: Difference between revisions
Jump to navigation
Jump to search
(Created page with "=External= * https://www.coursera.org/learn/algorithms-npcomplete/lecture/49MkW/the-traveling-salesman-problem * https://www.coursera.org/learn/algorithms-npcomplete/lecture/u...") |
|||
| Line 4: | Line 4: | ||
=Internal= | =Internal= | ||
* [[NP Completeness#Subjects|NP Completeness]] | * [[NP Completeness#Subjects|NP Completeness]] | ||
=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). | |||
Revision as of 19:32, 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).