Travelling Salesman Problem

[Greyguy1948]

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]

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]

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]

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?

 

[Greyguy1948]

Your code is very fast even on my Raspberry Pi:
13x13-> 69 ms
16x16 -> 582 ms

 

[Ken g6]

Not my code; I just knew what to search for. 🙂

 

[Greyguy1948]

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....