Travelling Salesman Problem

[zinujust]

When I try to input the distance matrix data from a textfile of size n=17, the program works, however, when I try to read a file of data N > 17, it gives me an array out of bound exception. How can I deal with that.

ftv35.txt testFile.txt

[williamfiset]

Hi,

I don’t think the issue is that the algorithm is broken, but rather that your input is too large. The TSP problem with DP can only be reasonably solved for up to ~25 nodes since O(n^22^n) for n = 25 is 20,971,520,000 operations which is pushing the limits of what a modern home computer can handle. The input test case you gave me has 36 nodes, so that’s 8.9 10^13 which is well beyond what any home computer can handle.

Since I know that TSP with DP can only handle ~25 nodes I encode the DP state using a 32 bit integer (instead of a 64 bits). This is probably why you’re experiencing out of bounds errors. I'll add a check to ensure that the input matrix isn't larger than 32.

On Sep 23, 2018, at 7:32 PM, zinujust notifications@github.com wrote:

When I try to input the distance matrix data from a textfile of size n=17, the program works, however, when I try to read a file of data N > 17, it gives me an array out of bound exception. How can I deal with that.

ftv35.txt https://github.com/williamfiset/Algorithms/files/2409473/ftv35.txt testFile.txt https://github.com/williamfiset/Algorithms/files/2409474/testFile.txt — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/williamfiset/Algorithms/issues/65, or mute the thread https://github.com/notifications/unsubscribe-auth/AFoCYP9kyM19pUodtqSBLvTTVMTF3qCrks5ueEREgaJpZM4W1_0S.

[williamfiset]

3f182d5529dc4279126cc6ddffe5dc9bff5ad8a2

[zinujust]

Thanks a lot sir, This was very helpful for me. If I may ask just one more question, how can I change it to 64 bit integer?

[williamfiset]

You can update the encoded DP state to use a 'long' type instead of an 'int' everywhere in the code, however, there's not much sense in doing so because any graph with more than 32 nodes will take too long to execute.