# Thread: Found exact solution for Traveling Salesmen Problem

1. Hi,

My name is Ilya Gazman. I found an exact solution for Traveling salesmen problem. Currently the best implementation according to wiki is Held–Karp algorithm that solves the problem in time O(N^2 * 2^N).

I believe that my algorithm can do this in O(N*C * 2^N) when C is a bit smaller than 1. I need your help to officially approve my work and update the wiki page.

So if this is interesting you here is how I did it:

Source code first, and now:

Lets say we want to solve a 6 cities route with the brout algorithm. There are (6-1)! options for that, we will need to test them all and return the shortest route founded. So it will look something like that(Cities names are: A, B, C, D, E, F):

Option 1 : A -> B -> C -> D -> E -> F -> A
Option 2 : A -> B -> C -> D -> F -> E -> A
Option 3 : A -> C -> B -> D -> E -> F -> A
Option 4 : A -> C -> B -> D -> F -> E -> A
.
.
Option 119
Option 120

Now I am saying that after calculating option 1, you can skip over options 2 and only calculate part of options 3 and 4. How do you do that? It's simple: When calculating option 1 you need to calculate what will be the shortest route starting from City D, finishing in City A, and going thru cities E, F. Now you can skip option 2 because you already calculated it in option 1. And when you start calculating options 3 and 4 you can stop when reaching City D, because you already know what would be the shortest route starting at city D, finishing in City A and going thru cities E, F.

This is the principle that I used in my algorithm. I run a brute algorithm and mapped all the sub results, those results are not sub routes, do not confuse there. They are just part of calculation that need to be done in order to find the shortest route. So each time I recognize I am doing the same calculation I used a solution from a map.

Here is an output of my algorithm running over 19 cities, (in the attached file you can find java code that implements it).
Code:
```Source(19)  [10.0,65.0, 34.0,52.0, 37.0,98.0, 39.0,44.0, 43.0,37.0, 45.0,89.0, 66.0,79.0, 69.0,74.0, 7.0,76.0, 70.0,15.0, 77.0,27.0, 78.0,11.0, 78.0,13.0, 80.0,5.0, 81.0,38.0, 82.0,64.0, 87.0,7.0, 90.0,61.0, 93.0,31.0]
Finish MapEngine test after 321550 mills
Created: 20801457

0) 295.5947584525372>   [10.0,65.0, 34.0,52.0, 39.0,44.0, 43.0,37.0, 70.0,15.0, 78.0,13.0, 78.0,11.0, 80.0,5.0, 87.0,7.0, 77.0,27.0, 93.0,31.0, 81.0,38.0, 90.0,61.0, 82.0,64.0, 69.0,74.0, 66.0,79.0, 45.0,89.0, 37.0,98.0, 7.0,76.0, 10.0,65.0]```
Source(19) is the input cities. It took my PC 321550 mills to calculate, (about 5 minutes). Created: 20801457 represent the number of atomic actions that the algorithm performed(about 20M actions). Map(3) speaks about the number of maps with 3 cities that been created. It created 2448 3 cities maps and used them 34272 times.

To calculate the efficiency of my algorithm all you need to do is to sum all the maps that he produce, then you will get the answer.

So the number of maps that my algorithm will produce with K cities size in N cities route will be: The number of times I can select the first city of my map: N, multiplies the number of times I can choose different selection of my cities from the remaining cities: (n-1)! / ((n - k - 1)! * (k-1)!). Thas come to n! / ((n - k - 1)! * (k-1)!). Assuming that creating a map of size 3 is an atomic action, then my algorithm efficiency will be the sum of all those maps.

So my algorithm have the next efficiency.

N * (N - 1) * (N - 2) / 2! + N * (N - 1) * (N - 2) * (N - 3) / 3! + N * (N - 1) * (N - 2) * (N - 3) (N -4) / 4! + ... N! / (N - 1)! = N * (N - 1) * (N - 2) / 2! + N * (N - 1) * (N - 2) * (N - 3) / 3! + N * (N - 1) * (N - 2) * (N - 3) (N -4) / 4! + ... N

Now lets solve this efficient algorithm with N from 7 to 100, and compare it to the previous results(result of N = 9 with N =8, result of N = 24 with N = 23). I found out that for big numbers of N the comparison result is 2. Then I did the same with the traditional dynamic programing algorithm efficiency. Here is the list of what I got:
Code:
```7   2.55769     2.72222     2.98397
8   2.40601     2.61224     2.74973
9   2.31562     2.53125     2.60507
10  2.2582      2.46913     2.50912
11  2.21972     2.42        2.44169
12  2.19258     2.38016     2.39191
13  2.17251     2.34722     2.35356
14  2.15701     2.31952     2.32293
15  2.14456     2.29591     2.29774
16  2.13424     2.27555     2.27652
17  2.12548     2.25781     2.25832
18  2.1179      2.24221     2.24248
19  2.11124     2.22839     2.22853
20  2.10533     2.21606     2.21614
21  2.10003     2.205       2.20503
22  2.09525     2.19501     2.19503
23  2.09091     2.18595     2.18596
24  2.08696     2.17769     2.17769
25  2.08333     2.17013     2.17014
26  2.08        2.1632      2.1632
27  2.07692     2.1568      2.1568
28  2.07407     2.15089     2.15089
29  2.07142     2.1454      2.1454
30  2.06896     2.1403      2.1403
31  2.06666     2.13555     2.13555
32  2.06451     2.13111     2.13111
33  2.0625      2.12695     2.12695
34  2.0606      2.12304     2.12304
35  2.05882     2.11937     2.11937
36  2.05714     2.11591     2.11591
37  2.05555     2.11265     2.11265
38  2.05405     2.10956     2.10956
39  2.05263     2.10664     2.10664
40  2.05128     2.10387     2.10387
41  2.05        2.10125     2.10125
42  2.04878     2.09875     2.09875
43  2.04761     2.09637     2.09637
44  2.04651     2.0941      2.0941
45  2.04545     2.09194     2.09194
46  2.04444     2.08987     2.08987
47  2.04347     2.0879      2.0879
48  2.04255     2.08601     2.08601
49  2.04166     2.0842      2.0842
50  2.04081     2.08246     2.08246
51  2.04        2.0808      2.0808
52  2.03921     2.0792      2.0792
53  2.03846     2.07766     2.07766
54  2.03773     2.07618     2.07618
55  2.03703     2.07475     2.07475
56  2.03636     2.07338     2.07338
57  2.03571     2.07206     2.07206
58  2.03508     2.07079     2.07079
59  2.03448     2.06956     2.06956
60  2.03389     2.06837     2.06837
61  2.03333     2.06722     2.06722
62  2.03278     2.06611     2.06611
63  2.03225     2.06503     2.06503
64  2.03174     2.06399     2.06399
65  2.03125     2.06298     2.06298
66  2.03076     2.06201     2.06201
67  2.0303      2.06106     2.06106
68  2.02985     2.06014     2.06014
69  2.02941     2.05925     2.05925
70  2.02898     2.05839     2.05839
71  2.02857     2.05755     2.05755
72  2.02816     2.05673     2.05673
73  2.02777     2.05594     2.05594
74  2.02739     2.05516     2.05516
75  2.02702     2.05441     2.05441
76  2.02666     2.05368     2.05368
77  2.02631     2.05297     2.05297
78  2.02597     2.05228     2.05228
79  2.02564     2.05161     2.05161
80  2.02531     2.05095     2.05095
81  2.025       2.05031     2.05031
82  2.02469     2.04968     2.04968
83  2.02439     2.04907     2.04907
84  2.02409     2.04848     2.04848
85  2.0238      2.0479      2.0479
86  2.02352     2.04733     2.04733
87  2.02325     2.04678     2.04678
88  2.02298     2.04624     2.04624
89  2.02272     2.04571     2.04571
90  2.02247     2.04519     2.04519
91  2.02222     2.04469     2.04469
92  2.02197     2.04419     2.04419
93  2.02173     2.04371     2.04371
94  2.0215      2.04324     2.04324
95  2.02127     2.04277     2.04277
96  2.02105     2.04232     2.04232
97  2.02083     2.04188     2.04188
98  2.02061     2.04144     2.04144
99  2.0204      2.04102     2.04102
100 2.0202      2.0406      2.0406```
Column 1 is N, column 2 is my algorithm efficiency compare, column 3 is dynamic programming algorithm compare and column 4 is my algorithm efficiency multiply N compare.

See how column 3 and 4 are almost the same. This is how I found it. Please verify my work, take a look at the code, tell me if you agree or not with me. If not please show me where my algorithm or my math is not working by exact sample.

2.

3. Originally Posted by Ilya.Gazman
Option 1 : A -> B -> C -> D -> E -> F -> A
Option 2 : A -> B -> C -> D -> F -> E -> A
Option 3 : A -> C -> B -> D -> E -> F -> A
Option 4 : A -> C -> B -> D -> F -> E -> A
.
.
Option 119
Option 120

Now I am saying that after calculating option 1, you can skip over options 2 and only calculate part of options 3 and 4. How do you do that? It's simple: When calculating option 1 you need to calculate what will be the shortest route starting from City D, finishing in City A, and going thru cities E, F. Now you can skip option 2 because you already calculated it in option 1. And when you start calculating options 3 and 4 you can stop when reaching City D, because you already know what would be the shortest route starting at city D, finishing in City A and going thru cities E, F.
Hi,
I wonder if you could clear up a problem I see with your idea.

"When calculating option 1 you need to calculate what will be the shortest route starting from City D, finishing in City A, and going thru cities E, F. Now you can skip option 2 because you already calculated it in option 1."
Option 1 doesn't calculate the shortest distance between D, E, F and A - it simply measures and records the total distance between D, E, F and A.
And, until Option 2 has measured the total distance between D, F, E and A, there is no way to know which route is shorter.

It seems to me that you are assuming that the total distance between D, E, F and A always equals the total distance between D, F, E and A - which is not correct.

4. You misunderstand me RedPanda. I am assuming that calculating 3 cities is an atomic action. In fact there is 2 options when building a three cities map. Lets say I have 3 cities A,B,C and I want to find what is the shortest pass from A thru B and C. So I need to check A,B,C and A,C,B. It will also be just two actions when I add another condition that I want to finish in city D. It will be A,B,C,D and A,C,B,D.

In my sample I am trying to calculate the shortest path for 6 cities. So when I am doing option 1, I am actually doing more than that. I am checking all the options there, witch includes option 2 also. Nothing saved yet... How ever when I am going to option 3 I recognize the same 3 cities at then end, so I am actually saving 1 calculation. and same is with option 4. Because I know what would be the shortest path from D to A thru F,E I can use a map that I found when calculating option 1 and save those calculations.

It has more dramatic effect when it comes to bigger maps. If I was trying to solve a 7 cities map, I would be able to use 4 cities map to save my time, like this: If I will find what is shortest path from A to E thru B,C,D, I can use it later to save my calculations when trying all the options that start with F,G,A and End with F going thru B,C,D. This is 6 options actually.

I hope this is clear now.

5. Originally Posted by Ilya.Gazman
You misunderstand me RedPanda. I am assuming that calculating 3 cities is an atomic action. In fact there is 2 options when building a three cities map. Lets say I have 3 cities A,B,C and I want to find what is the shortest pass from A thru B and C. So I need to check A,B,C and A,C,B. It will also be just two actions when I add another condition that I want to finish in city D. It will be A,B,C,D and A,C,B,D.

In my sample I am trying to calculate the shortest path for 6 cities. So when I am doing option 1, I am actually doing more than that. I am checking all the options there, witch includes option 2 also. Nothing saved yet... How ever when I am going to option 3 I recognize the same 3 cities at then end, so I am actually saving 1 calculation. and same is with option 4. Because I know what would be the shortest path from D to A thru F,E I can use a map that I found when calculating option 1 and save those calculations.

It has more dramatic effect when it comes to bigger maps. If I was trying to solve a 7 cities map, I would be able to use 4 cities map to save my time, like this: If I will find what is shortest path from A to E thru B,C,D, I can use it later to save my calculations when trying all the options that start with F,G,A and End with F going thru B,C,D. This is 6 options actually.
So, how are you reducing the number of iterations?
If you are still having to parse each path to see if it contains subsets of valid paths, how is that going to be quicker than a branch and bound technique which doesn't parse all paths?

6. I think you need to run the code to understand this better. For my 6 cities example that I gave, I have a total of 120 options, my algorithm will create 30 maps of 3 cities, it will use them 30 times. And it will save 15 actions.

For bigger input like 20 cities, the saving will be (n - 1)! / (N * 2^N) ,about 12,000,000,000 calculations.

7. <deleted>

Going to have another think later.

8. Originally Posted by Ilya.Gazman
This is the principle that I used in my algorithm. I run a brute algorithm and mapped all the sub results, those results are not sub routes, do not confuse there. They are just part of calculation that need to be done in order to find the shortest route. So each time I recognize I am doing the same calculation I used a solution from a map.
Could you explain what the sub results are?
Are they a list of invalid (i.e. know to be too long) 3 city permutations?
Or is it a list of each 3 city permutation and its total distance?
Could you maybe post a copy of them?