5 Replies - 6592 Views - Last Post: 18 October 2013 - 08:38 AM

#1 Ilya.Gazman   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 13-October 13

Found exact solution for TSP

Posted 13 October 2013 - 09:46 AM

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:

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).
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
Map(3)  Write    2448       Read     34272
Map(4)  Write    12240      Read     159120
Map(5)  Write    42840      Read     514080
Map(6)  Write    111384     Read     1225224
Map(7)  Write    222768     Read     2227680
Map(8)  Write    350064     Read     3150576
Map(9)  Write    437580     Read     3500640
Map(10) Write    437580     Read     3084270
Map(11) Write    352185     Read     2344256
Map(12) Write    245131     Read     1382525
Map(13) Write    135638     Read     570522
Map(14) Write    54320      Read     156758
Map(15) Write    15077      Read     27058
Map(16) Write    2809       Read     2087
Map(17) Write    306        Read     0
Map(18) Write    18         Read     0
Map(19) Write    1          Read     0

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

Attached File(s)



Is This A Good Question/Topic? 0
  • +

Replies To: Found exact solution for TSP

#2 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12646
  • View blog
  • Posts: 45,819
  • Joined: 27-December 08

Re: Found exact solution for TSP

Posted 17 October 2013 - 10:32 PM

Quote

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.

Do you know how Held-Karp actually works? The 2N step occurs initially. Evaluate the two lowest cost edges for each vertex. Now choose the vertex whose two lowest cost edges sum to the smallest value. That's your starting vertex. The N2 step is the MST step, with a couple of added constraints. Sure you can knock a constant off the MST algorithm based on the underlying data structures (adjacency list vs. adjacency matrix, as an example), but I wouldn't be inclined to update the Wiki page based on your work. I don't think you've done anything groundbreaking if your complexity analysis is correct.

I haven't actually torn through your code myself, nor do I really have enough time to look through all of it. I did download it, and there is quite a bit there. It certainly does look like you've put a lot of work into it. The groundbreaking task is to reduce the 2N term to something bounded by a polynomial on N.

Edit: Also, by the definition of Big-O, CN * 2N = O(N2 * 2N).

This post has been edited by macosxnerd101: 17 October 2013 - 10:44 PM

Was This Post Helpful? 0
  • +
  • -

#3 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11651
  • View blog
  • Posts: 19,801
  • Joined: 19-March 11

Re: Found exact solution for TSP

Posted 18 October 2013 - 12:55 AM

Quote

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.


I haven't examined your code, but this looks suspiciously like a dynamic programming approach. Unfortunately, dynamic programming isn't super useful here, since what you're really trying to do in that case is to get this down to something where you have a solved sub-problem, and there's no reason to suppose that these subproblems stay solved. So the hard part isn't calculating the distance a>b>c>d, the hard part is figuring out that a>b>c>d is an interesting distance. There's no reason to suppose it's any more interesting than any other distance, so this doesn't do you a lot of good.
Was This Post Helpful? 0
  • +
  • -

#4 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7056
  • View blog
  • Posts: 23,986
  • Joined: 05-May 12

Re: Found exact solution for TSP

Posted 18 October 2013 - 06:03 AM

Interesting comments about this same post in stackoverflow.com and cs.stackexchange.com

There are other copies of this post. Just search for "It took my PC 321550 mills to calculate". In one forum, I found it interesting that people started optimizing the posted code without actually taking time to understand the underlying algorithm.
Was This Post Helpful? 0
  • +
  • -

#5 Ilya.Gazman   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 13-October 13

Re: Found exact solution for TSP

Posted 18 October 2013 - 08:20 AM

Me too
Was This Post Helpful? 0
  • +
  • -

#6 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11651
  • View blog
  • Posts: 19,801
  • Joined: 19-March 11

Re: Found exact solution for TSP

Posted 18 October 2013 - 08:38 AM

Probably for different reasons, though.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1