5.0 | 1 rating Rate this file 65 Downloads (last 30 days) File Size: 3.04 KB File ID: #31454

Dynamic Programming solution to the TSP



This function solves the Traveling Salesman Problem (TSP) using Dynamic programming (DP).

| Watch this File

File Information

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.

MATLAB release MATLAB 7.6 (R2008a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (7)
17 Nov 2012 Thanapan  
19 May 2012 Leonardo BOrges

Cool i need this solutions for my study academic, thak you

22 Feb 2012 Vahid


22 Feb 2012 Elad Kivelevitch

As I said, I haven't tested it for an asymmetric TSP. You will need to pass a list of cities with n rows and 2 columns. This list will not be used in calculating the Dmatrix, but will be used for knowing the number of cities.

You know, it's a MATLAB code that you could modify and try to run your own versions...

22 Feb 2012 Vahid

If I put an assymetric Dmatrix, what should I put as the cities coordinates?

14 Feb 2012 Elad Kivelevitch

Correct. Just a symmetric TSP and only for a limited number of cities.

However, now that I think about it, I have no idea what happens if you use an asymmetric Dmatrix. Maybe it will work. Try it sometime.

14 Feb 2012 Vahid

Thanks for the code. Is is only working for symmetric TSP?

Contact us