Dynamic Programming solution to the TSP

Versione 1.0.0.0 (3,04 KB) da Elad Kivelevitch
This function solves the Traveling Salesman Problem (TSP) using Dynamic programming (DP).
4.7
(7)
2,8K download
Aggiornato 15 mag 2011

Visualizza la licenza

The function is based on the paper by Held and Karp from 1962. The DP is guaranteed to provide the accurate (optimal) result to the TSP, but the time complexity of this algorithm is O(2^n n^2), which limits the use of this algorithm to 15 cities or less.

NOTE: For reasonable runtime, please do not try to calculate a tour of more than 13 cities. DP is not for large sets of cities.

Cita come

Elad Kivelevitch (2025). Dynamic Programming solution to the TSP (https://it.mathworks.com/matlabcentral/fileexchange/31454-dynamic-programming-solution-to-the-tsp), MATLAB Central File Exchange. Recuperato .

Compatibilità della release di MATLAB
Creato con R2008a
Compatibile con qualsiasi release
Compatibilità della piattaforma
Windows macOS Linux
Tag Aggiungi tag

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Versione Pubblicato Note della release
1.0.0.0