Travelling Salesman Problem

Greyguy1948

Member
Nov 29, 2008
156
16
91
TSP_brute

This code is using a 5x5 plan and all is very fast for a modern cpu.
I have increased the distace plan up to 12x12 and it works fine with 12! paths.
But at 13x13 and 14x14 it doesn't work...not 13! or 14!
Paths must be declared as long instead of int but still it doesn't work.
Any ideas?
 

Greyguy1948

Member
Nov 29, 2008
156
16
91
This is a 13x13 distance plan

0 3 4 2 7 9 8 5 8 6 4 4 9
3 0 4 6 3 9 5 6 3 2 4 5 9
4 4 0 5 8 7 3 4 9 3 9 1 9
2 6 5 0 6 5 6 9 7 1 5 5 9
7 3 8 6 0 3 7 8 5 4 8 8 9
9 9 7 5 3 0 4 5 4 9 7 7 9
8 5 3 6 7 4 0 6 3 2 3 3 9
5 6 4 9 8 5 6 0 1 7 4 4 9
8 3 9 7 5 4 3 1 0 5 9 9 9
6 2 3 1 4 9 2 7 5 0 3 3 9
4 4 1 5 8 7 3 4 9 3 0 6 8
4 5 9 5 8 7 3 4 9 3 6 0 8
9 9 9 9 9 9 9 9 9 9 8 8 0
 

Ken g6

Programming Moderator, Elite Member
Moderator
Dec 11, 1999
16,218
3,796
75
Are you sure it doesn't work, or is it just too slow? Brute force is a terrible way to solve TSP. Branch-and-bound is slightly better. I used the code from here and solved your 13x13:

Total Cost is 41

1 -> 4
4 -> 10
10 -> 7
7 -> 9
9 -> 8
8 -> 11
11 -> 3
3 -> 12
12 -> 13
13 -> 6
6 -> 5
5 -> 2
2 -> 1

When I accidentally broke it by using 0's instead of INFs the first time, it took several seconds. An unoptimized program might take long enough that you'd think it was broken.

If for some reason you need the brute-force thing, are you sure you got all the correct ints changed to longs? How is it broken? Post your version of the code.
 

Greyguy1948

Member
Nov 29, 2008
156
16
91
Thank you for your answer!
I'm using Raspbery Pi 3 and it is slow but the problem is to use long long for some variables.
long is the same as int with my compiler.
paths long long
Not working!
Number of paths must be around 6000 mega but I get 1900 mega.
Some other long long variable must be used?
 

Ken g6

Programming Moderator, Elite Member
Moderator
Dec 11, 1999
16,218
3,796
75
Not my code; I just knew what to search for. :)
 

Greyguy1948

Member
Nov 29, 2008
156
16
91
OK branch-and-bound is very fast but not the same on ARM and X86_64 with gcc compiler.
With ARM (RPi 3) I have no problem with optimizing -O1, -O2 or -O3 and it works up to 18x18.
With core i7-8700 it works with 22x22 but all optimizing result in segmentation fault....