Traveling Salesman Problem

From NovaOrdis Knowledge Base
Revision as of 19:38, 26 November 2021 by Ovidiu (talk | contribs) (→‎Internal)
Jump to navigation Jump to search

External

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).