Dynamic Programming solution to the TSP
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.
Cite As
Elad Kivelevitch (2024). Dynamic Programming solution to the TSP (https://www.mathworks.com/matlabcentral/fileexchange/31454-dynamic-programming-solution-to-the-tsp), MATLAB Central File Exchange. Retrieved .
MATLAB Release Compatibility
Platform Compatibility
Windows macOS LinuxCategories
- AI, Data Science, and Statistics > Statistics and Machine Learning Toolbox > Cluster Analysis and Anomaly Detection > Nearest Neighbors >
- MATLAB > Mathematics > Graph and Network Algorithms > Shortest Path > Traveling Salesman (TSP) >
- Mathematics and Optimization > Optimization Toolbox > Linear Programming and Mixed-Integer Linear Programming > Solver-Based Linear Programming >
Tags
Acknowledgements
Inspired: Travelling Salesman Problem by Dynamic Programming
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Discover Live Editor
Create scripts with code, output, and formatted text in a single executable document.
Version | Published | Release Notes | |
---|---|---|---|
1.0.0.0 |