Math Is Fun Forum
You are not logged in.
- Topics: Active | Unanswered
Pages: 1
#1 2007-08-11 06:24:47
- Kargoneth
- Member
- Registered: 2007-08-11
- Posts: 33
Travelling Salesman Problem Solution Speed
No matter where I go, I see people mumbling about the slow speed of solving the TSP (Travelling Salesman Problem). I do not see how that could be very difficult unless the route between two nodes can be different depending on the direction.
When the distance between two nodes is constant, no matter the direction, I have found a method which takes approximately (n ^ 2) / 2 - 3 comparisons... extremely fast compared to the 2 ^ n rubbish I hear people mumbling about.
Is this 'fast' compared to other algorithms people have developed (I am not very adept at using search engines... too many irrelevant results)? I have not found any other forums which have this topic in them and most sites
(Note: I will keep the algorithm to myself until I am certain it is worthy of being published)
Offline
#2 2007-08-11 07:34:09
- mathsyperson
- Moderator
- Registered: 2005-06-22
- Posts: 4,900
Re: Travelling Salesman Problem Solution Speed
You might want to wait until someone more knowledgeable comes on, but I'm pretty sure that the fastest algorithm we have so far uses exponential time, and so if yours works then it would be a massive discovery.
Why did the vector cross the road?
It wanted to be normal.
Offline
#3 2007-08-11 11:49:45
- MathsIsFun
- Administrator
- Registered: 2005-01-21
- Posts: 7,713
Re: Travelling Salesman Problem Solution Speed
That would indeed be spectacular. It would mean the solution is in polynomial time ("P" not "NP-complete").
The topic is a well-researched one, with lots of different algorithms.
I am not an expert, however. My experience with this was writing a Genetic Algorithm solution for a company that supplied bars cut to size (from standard stock). They typically had about 10% wastage and I reduced that to about 3%. My solution was not optimum, but close enough (they didn't want to wait for more that a few minutes computing time before starting cutting).
There is a standard set of data you can test your algorithm against called TSPLIB: http://www.iwr.uni-heidelberg.de/groups … index.html
"The physicists defer only to mathematicians, and the mathematicians defer only to God ..." - Leon M. Lederman
Offline
#4 2007-08-11 12:14:18
- mikau
- Member
- Registered: 2005-08-22
- Posts: 1,504
Re: Travelling Salesman Problem Solution Speed
just a guess but maybe this stipulation
When the distance between two nodes is constant
does not hold in the general 2^n algorithms?
A logarithm is just a misspelled algorithm.
Offline
#5 2007-08-11 14:35:54
- Kargoneth
- Member
- Registered: 2007-08-11
- Posts: 33
Re: Travelling Salesman Problem Solution Speed
just a guess but maybe this stipulation
When the distance between two nodes is constant
does not hold in the general 2^n algorithms?
So it would appear. I have noticed that the amount of searches is exponential for that version... Once I confirm that my method for standard TSP is sound, I will delve deeper into this version.
Hrm... I wonder if I am confusing computational time with the total paths... I will have to investigate...
Total Paths = (n ^ 2 - n) / 2 - 3 where n is an integer greater than 3
10000 nodes = 49994997 paths... so as long as my algorithm is a constant multiple of the total paths, it should work well.
Let's see...
Nodes, Main function executions
3, 2
4, 5
5, 9
6, 14
7, 20
Err... what is that...
(x ^ 2 + x) / 4 - 1
Not too bad... my main function is executed a number of times equal to
Note that this is a guess of total executions... once I finish my program I will have it count them for me
Last edited by Kargoneth (2007-08-11 15:13:14)
Offline
#6 2007-08-11 16:30:16
- MathsIsFun
- Administrator
- Registered: 2005-01-21
- Posts: 7,713
Re: Travelling Salesman Problem Solution Speed
Note that this is a guess of total executions... once I finish my program I will have it count them for me
That seems to be a reasonable thing to do.
Sometimes in practice you can get polynomial time, depending on the data you are working on, but a deeper analysis may show something else though.
In any event, the pursuit of more efficient algorithms is very worthwhile.
"The physicists defer only to mathematicians, and the mathematicians defer only to God ..." - Leon M. Lederman
Offline
#7 2007-08-12 03:23:21
- mathsyperson
- Moderator
- Registered: 2005-06-22
- Posts: 4,900
Re: Travelling Salesman Problem Solution Speed
Let's see...
Nodes, Main function executions
3, 2
4, 5
5, 9
6, 14
7, 20Err... what is that...
(x ^ 2 + x) / 4 - 1
Looks more like (x² - x)/2 - 1 to me. Still polynomial time though, that's the main thing.
You say you want to keep the algorithm to yourself until you know it's worthy of publishing, but you might have a problem there. If it really works then it is a great discovery, but the only way to know whether it does is to show it to other people and see if they can find flaws in it. So in other words, to find out if it's worthy of publishing, you first need to publish. 
Why did the vector cross the road?
It wanted to be normal.
Offline
#8 2007-08-12 15:25:43
- Ricky
- Moderator
- Registered: 2005-12-04
- Posts: 3,791
Re: Travelling Salesman Problem Solution Speed
Total Paths = (n ^ 2 - n) / 2 - 3 where n is an integer greater than 3
How did you get that? Given n cities, we first select the first city to go to, then the second, then the third, and so on. As such, since we can't visit a city twice, this is simply (n-1)! (take out the first city). You start at some city and have n-1 choices for your next jump, then n-2, then n-3, and so on. Now this will actually double the number of trips, because it will find a route a, b, c, d, e and count as a different route e, d, c, b, a. However, these are exactly the same routes.
So the answer is (n-1)!/2 possibilites.
You say you want to keep the algorithm to yourself until you know it's worthy of publishing, but you might have a problem there. If it really works then it is a great discovery, but the only way to know whether it does is to show it to other people and see if they can find flaws in it. So in other words, to find out if it's worthy of publishing, you first need to publish.
He has actually already told you his algorithm... try every solution. It's just that he has a problem space size wrong.
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
Offline
#9 2007-08-13 23:37:14
- Anthony.R.Brown
- Banned
- Registered: 2006-11-16
- Posts: 516
Re: Travelling Salesman Problem Solution Speed
To Kargoneth
Quote:" No matter where I go, I see people mumbling about the slow speed of solving the TSP (Travelling Salesman Problem). I do not see how that could be very difficult unless the route between two nodes can be different depending on the direction. "
A.R.B
A much easier way to solve the TSP problem is to use a Ball of string! no Math needed!!............................................................
Offline
#10 2007-08-13 23:41:18
- mathsyperson
- Moderator
- Registered: 2005-06-22
- Posts: 4,900
Re: Travelling Salesman Problem Solution Speed
And what would you do with that ball of string?
If you measure all the routes, then that's still n! routes you need to measure, but as you're using string instead of a computer, then you get maybe 0.1 routes per second measured instead of millions.
Why did the vector cross the road?
It wanted to be normal.
Offline
#11 2007-08-13 23:49:53
- Anthony.R.Brown
- Banned
- Registered: 2006-11-16
- Posts: 516
Re: Travelling Salesman Problem Solution Speed
Quote:" And what would you do with that ball of string?
If you measure all the routes, then that's still n! routes you need to measure, but as you're using string instead of a computer, then you get maybe 0.1 routes per second measured instead of millions. "
A.R.B
Simple Solutions Beat Math/Computers etc. Hands Down!.......................................................................................................
Offline
#12 2007-08-14 10:25:34
- Kargoneth
- Member
- Registered: 2007-08-11
- Posts: 33
Re: Travelling Salesman Problem Solution Speed
I used excel to predict my program's loop counts... it is correct...
Now I must see if my program is correct
Facts Loop Iterations
Nodes Possible Paths Outer Inner Total Nodes ^ 2
1 0
2 1
3 1 0 0 0 9
4 3 1 3 4 16
5 12 2 7 9 25
6 60 3 12 15 36
7 360 4 18 22 49
8 2520 5 25 30 64
9 20160 6 33 39 81
10 181440 7 42 49 100
11 1814400 8 52 60 121
12 19958400 9 63 72 144
13 239500800 10 75 85 169
14 3113510400 11 88 99 196
15 43589145600 12 102 114 225
16 6.53837E+11 13 117 130 256
17 1.04614E+13 14 133 147 289
18 1.77844E+14 15 150 165 324
19 3.20119E+15 16 168 184 361
20 6.08226E+16 17 187 204 400
21 1.21645E+18 18 207 225 441
22 2.55455E+19 19 228 247 484
23 5.62E+20 20 250 270 529
24 1.2926E+22 21 273 294 576
25 3.10224E+23 22 297 319 625
26 7.75561E+24 23 322 345 676
27 2.01646E+26 24 348 372 729
28 5.44443E+27 25 375 400 784
29 1.52444E+29 26 403 429 841
30 4.42088E+30 27 432 459 900
31 1.32626E+32 28 462 490 961
32 4.11142E+33 29 493 522 1024
33 1.31565E+35 30 525 555 1089
34 4.34166E+36 31 558 589 1156
35 1.47616E+38 32 592 624 1225
36 5.16657E+39 33 627 660 1296
37 1.85997E+41 34 663 697 1369
38 6.88188E+42 35 700 735 1444
39 2.61511E+44 36 738 774 1521
40 1.01989E+46 37 777 814 1600
41 4.07958E+47 38 817 855 1681
42 1.67263E+49 39 858 897 1764
43 7.02503E+50 40 900 940 1849
44 3.02076E+52 41 943 984 1936
45 1.32914E+54 42 987 1029 2025
46 5.98111E+55 43 1032 1075 2116
47 2.75131E+57 44 1078 1122 2209
48 1.29312E+59 45 1125 1170 2304
49 6.20696E+60 46 1173 1219 2401
50 3.04141E+62 47 1222 1269 2500
51 1.5207E+64 48 1272 1320 2601
52 7.75559E+65 49 1323 1372 2704
53 4.03291E+67 50 1375 1425 2809
54 2.13744E+69 51 1428 1479 2916
55 1.15422E+71 52 1482 1534 3025
56 6.3482E+72 53 1537 1590 3136
57 3.55499E+74 54 1593 1647 3249
58 2.02635E+76 55 1650 1705 3364
59 1.17528E+78 56 1708 1764 3481
60 6.93416E+79 57 1767 1824 3600
61 4.16049E+81 58 1827 1885 3721
62 2.5379E+83 59 1888 1947 3844
63 1.5735E+85 60 1950 2010 3969
64 9.91304E+86 61 2013 2074 4096
65 6.34435E+88 62 2077 2139 4225
66 4.12383E+90 63 2142 2205 4356
67 2.72172E+92 64 2208 2272 4489
68 1.82356E+94 65 2275 2340 4624
69 1.24002E+96 66 2343 2409 4761
70 8.55612E+97 67 2412 2479 4900
71 5.9893E+99 68 2482 2550 5041
72 4.2524E+101 69 2553 2622 5184
73 3.0617E+103 70 2625 2695 5329
74 2.2351E+105 71 2698 2769 5476
75 1.6539E+107 72 2772 2844 5625
76 1.2405E+109 73 2847 2920 5776
77 9.4275E+110 74 2923 2997 5929
78 7.2592E+112 75 3000 3075 6084
79 5.6621E+114 76 3078 3154 6241
80 4.4731E+116 77 3157 3234 6400
81 3.5785E+118 78 3237 3315 6561
82 2.8986E+120 79 3318 3397 6724
83 2.3768E+122 80 3400 3480 6889
84 1.9728E+124 81 3483 3564 7056
85 1.6571E+126 82 3567 3649 7225
86 1.4086E+128 83 3652 3735 7396
87 1.2114E+130 84 3738 3822 7569
88 1.0539E+132 85 3825 3910 7744
89 9.2741E+133 86 3913 3999 7921
90 8.254E+135 87 4002 4089 8100
91 7.4286E+137 88 4092 4180 8281
92 6.76E+139 89 4183 4272 8464
93 6.2192E+141 90 4275 4365 8649
94 5.7839E+143 91 4368 4459 8836
95 5.4368E+145 92 4462 4554 9025
96 5.165E+147 93 4557 4650 9216
97 4.9584E+149 94 4653 4747 9409
98 4.8096E+151 95 4750 4845 9604
99 4.7134E+153 96 4848 4944 9801
100 4.6663E+155 97 4947 5044 10000
101 4.6663E+157 98 5047 5145 10201
102 4.713E+159 99 5148 5247 10404
103 4.8072E+161 100 5250 5350 10609
104 4.9515E+163 101 5353 5454 10816
105 5.1495E+165 102 5457 5559 11025
106 5.407E+167 103 5562 5665 11236
107 5.7314E+169 104 5668 5772 11449
108 6.1326E+171 105 5775 5880 11664
109 6.6232E+173 106 5883 5989 11881
110 7.2193E+175 107 5992 6099 12100
111 7.9412E+177 108 6102 6210 12321
112 8.8148E+179 109 6213 6322 12544
113 9.8725E+181 110 6325 6435 12769
114 1.1156E+184 111 6438 6549 12996
115 1.2718E+186 112 6552 6664 13225
116 1.4625E+188 113 6667 6780 13456
117 1.6966E+190 114 6783 6897 13689
118 1.985E+192 115 6900 7015 13924
119 2.3423E+194 116 7018 7134 14161
120 2.7873E+196 117 7137 7254 14400
121 3.3448E+198 118 7257 7375 14641
122 4.0471E+200 119 7378 7497 14884
123 4.9375E+202 120 7500 7620 15129
124 6.0732E+204 121 7623 7744 15376
125 7.5307E+206 122 7747 7869 15625
126 9.4134E+208 123 7872 7995 15876
127 1.1861E+211 124 7998 8122 16129
128 1.5063E+213 125 8125 8250 16384
129 1.9281E+215 126 8253 8379 16641
130 2.4873E+217 127 8382 8509 16900
131 3.2334E+219 128 8512 8640 17161
132 4.2358E+221 129 8643 8772 17424
133 5.5912E+223 130 8775 8905 17689
134 7.4364E+225 131 8908 9039 17956
135 9.9647E+227 132 9042 9174 18225
136 1.3452E+230 133 9177 9310 18496
137 1.8295E+232 134 9313 9447 18769
138 2.5064E+234 135 9450 9585 19044
139 3.4589E+236 136 9588 9724 19321
140 4.8079E+238 137 9727 9864 19600
141 6.731E+240 138 9867 10005 19881
142 9.4907E+242 139 10008 10147 20164
143 1.3477E+245 140 10150 10290 20449
144 1.9272E+247 141 10293 10434 20736
145 2.7751E+249 142 10437 10579 21025
146 4.024E+251 143 10582 10725 21316
147 5.875E+253 144 10728 10872 21609
148 8.6362E+255 145 10875 11020 21904
149 1.2782E+258 146 11023 11169 22201
150 1.9045E+260 147 11172 11319 22500
151 2.8567E+262 148 11322 11470 22801
152 4.3136E+264 149 11473 11622 23104
153 6.5567E+266 150 11625 11775 23409
154 1.0032E+269 151 11778 11929 23716
155 1.5449E+271 152 11932 12084 24025
156 2.3946E+273 153 12087 12240 24336
157 3.7355E+275 154 12243 12397 24649
158 5.8648E+277 155 12400 12555 24964
159 9.2664E+279 156 12558 12714 25281
160 1.4734E+282 157 12717 12874 25600
161 2.3574E+284 158 12877 13035 25921
162 3.7954E+286 159 13038 13197 26244
163 6.1485E+288 160 13200 13360 26569
164 1.0022E+291 161 13363 13524 26896
165 1.6436E+293 162 13527 13689 27225
166 2.712E+295 163 13692 13855 27556
167 4.5018E+297 164 13858 14022 27889
168 7.5181E+299 165 14025 14190 28224
169 1.263E+302 166 14193 14359 28561
170 2.1345E+304 167 14362 14529 28900
171 3.6287E+306 168 14532 14700 29241Offline
#13 2007-08-14 11:15:45
- Ricky
- Moderator
- Registered: 2005-12-04
- Posts: 3,791
Re: Travelling Salesman Problem Solution Speed
You're going to have to explain what the column names mean. Facts nodes? Loop Outer? Iterations Inner?
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
Offline
#14 2007-08-14 12:28:04
- Kargoneth
- Member
- Registered: 2007-08-11
- Posts: 33
Re: Travelling Salesman Problem Solution Speed
Whoops, sorry.
Nodes = amount of nodes to test
Possible paths = the total possible paths (good and bad) for the amount of nodes
Outer = how many times my program's outer loop is executed
Inner = how many times my program's inner loop is executed
Total = total of the outer and inner loops
Nodes ^ 2 = just to compare to my total loop executions
Bad news is, that my algorithm (at least in so far as I have coded it) has failed... a shorter path existed...
Good news is that I will see if I just screwed up with the logic, or if my entire idea is flawed (more than 6 nodes seems to cause my algorithm to have a seizure sometimes...)
Offline
#15 2007-08-14 13:56:44
- MathsIsFun
- Administrator
- Registered: 2005-01-21
- Posts: 7,713
Re: Travelling Salesman Problem Solution Speed
Keep going ... you may end up finding something.
PS: don't you need to multiply inner by outer loops (if no early breaks)
"The physicists defer only to mathematicians, and the mathematicians defer only to God ..." - Leon M. Lederman
Offline
#16 2007-08-14 15:38:09
- Kargoneth
- Member
- Registered: 2007-08-11
- Posts: 33
Re: Travelling Salesman Problem Solution Speed
Since the inner and outer loops have a variable amount of iterations (the inner varies as the program runs), I just total them as they are executed; no need for multiplication 
Offline
#17 2007-08-15 01:21:41
- Ricky
- Moderator
- Registered: 2005-12-04
- Posts: 3,791
Re: Travelling Salesman Problem Solution Speed
Does possible paths mean only the ones you check, or all paths that could ever be taken? If it is the later, it's wrong.
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
Offline
#18 2007-08-18 16:45:21
- Kargoneth
- Member
- Registered: 2007-08-11
- Posts: 33
Re: Travelling Salesman Problem Solution Speed
Possible paths is the amount of paths that can be taken, where the order of the nodes moved to is identical. Where the loop for one path equals another, they are considered identical, as well as situations where they are 100% reversed.
With 3 nodes:
1 path:
abc = bca = cab = cba = acb = bac
With 4 nodes:
3 paths:
abcd = bcda = cdab = dabc = dcba = adcb = badc = cbad
abdc = bdca = dcab = cabd = cdba = acdb = bacd = dbac
adbc = dbca = bcad = cadb = cbda = acdb = dacb = bdac
Offline
#19 2007-08-18 20:58:54
- mathsyperson
- Moderator
- Registered: 2005-06-22
- Posts: 4,900
Re: Travelling Salesman Problem Solution Speed
Surely that means that the amount of paths you would need to check is (n-1)!/2. Slightly better than n!, but still factorial time.
Why did the vector cross the road?
It wanted to be normal.
Offline
#20 2007-08-19 00:37:51
- Ricky
- Moderator
- Registered: 2005-12-04
- Posts: 3,791
Re: Travelling Salesman Problem Solution Speed
That is incorrect.
AB = 5
AC = 3
BC = 4
Then the path abc has a cost of 9 whereas acb has a cost of 7.
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
Offline
#21 2007-08-19 00:58:54
- mathsyperson
- Moderator
- Registered: 2005-06-22
- Posts: 4,900
Re: Travelling Salesman Problem Solution Speed
Ah, excellent point. Kargoneth's reasoning only works if the problem is to find a cycle rather than a path.
Why did the vector cross the road?
It wanted to be normal.
Offline
#22 2007-08-19 01:50:52
- Ricky
- Moderator
- Registered: 2005-12-04
- Posts: 3,791
Re: Travelling Salesman Problem Solution Speed
Ah, sorry, it is a circuit in the problem. And (n-1)!/2 isn't really considered better than n! when it comes to theoretical computational problems. They are actually exactly the same.
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
Offline
#23 2007-08-19 02:59:37
- Kargoneth
- Member
- Registered: 2007-08-11
- Posts: 33
Re: Travelling Salesman Problem Solution Speed
That is incorrect.
AB = 5
AC = 3
BC = 4Then the path abc has a cost of 9 whereas acb has a cost of 7.
I always thought the problem entailed returning to where you started from after reaching the last city... in which case:
ABC (and back to A) = 5 + 4 + 3 = 12
ACB (and back to A) = 3 + 4 + 5 = 12
Probably a false assumption on my part. Whoops
Offline
#24 2007-08-19 03:05:39
- Ricky
- Moderator
- Registered: 2005-12-04
- Posts: 3,791
Re: Travelling Salesman Problem Solution Speed
Nope, you were the right one. Read my last post.
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
Offline
Pages: 1