Ilya Gazman Posted October 13, 2013 Posted October 13, 2013 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). 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.
ralphyralph Posted October 16, 2013 Posted October 16, 2013 I have to ask...why post this here? There are many other communities (Stack Exchange, your respective University) that would be a much better place to test your theories! With regards to the problem, Wikipedia is incorrect if it states that the fastest algorithm solves in O(n^2 * 2^n) speed. The lower bound on computation speed is O (C * 2^n) where C is a constant > 1. I didn't validate whether your algorithm actually converges in the time you stated, but if it does good on you for finding a novel algorithm that converges at that speed! Tha's a great accomplishment, but It doesn't redefine the lower bound. However, if you can implement an algorithm in sub O(2^n) time, that would be a major breakthrough.
drighanchu Posted October 21, 2013 Posted October 21, 2013 the best way to verify is to write a journal/conference paper and submit, and get the community feedback. like here -- 1. http://www.journals.elsevier.com/information-processing-letters/ 2. http://link.springer.com/journal/453
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now