Notices
Results 1 to 7 of 7
Like Tree1Likes
  • 1 Post By RedPanda

Thread: Found exact solution for Traveling Salesmen Problem

  1. #1 Found exact solution for Traveling Salesmen Problem 
    New Member
    Join Date
    Oct 2013
    Posts
    3
    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
    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:
    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.


    Reply With Quote  
     

  2.  
     

  3. #2  
    ▼▼ dn ʎɐʍ sıɥʇ ▼▼ RedPanda's Avatar
    Join Date
    Aug 2012
    Location
    UK
    Posts
    2,737
    Quote Originally Posted by Ilya.Gazman View Post
    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.


    John Galt likes this.
    SayBigWords.com/say/3FC

    "And, behold, I come quickly;" Revelation 22:12

    "Religions are like sausages. When you know how they are made, you no longer want them."
    Reply With Quote  
     

  4. #3  
    New Member
    Join Date
    Oct 2013
    Posts
    3
    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.
    Reply With Quote  
     

  5. #4  
    ▼▼ dn ʎɐʍ sıɥʇ ▼▼ RedPanda's Avatar
    Join Date
    Aug 2012
    Location
    UK
    Posts
    2,737
    Quote Originally Posted by Ilya.Gazman View Post
    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?
    SayBigWords.com/say/3FC

    "And, behold, I come quickly;" Revelation 22:12

    "Religions are like sausages. When you know how they are made, you no longer want them."
    Reply With Quote  
     

  6. #5  
    New Member
    Join Date
    Oct 2013
    Posts
    3
    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.
    Reply With Quote  
     

  7. #6  
    ▼▼ dn ʎɐʍ sıɥʇ ▼▼ RedPanda's Avatar
    Join Date
    Aug 2012
    Location
    UK
    Posts
    2,737
    <deleted>
    I made a mistake.

    Going to have another think later.
    Last edited by RedPanda; October 14th, 2013 at 01:06 PM.
    SayBigWords.com/say/3FC

    "And, behold, I come quickly;" Revelation 22:12

    "Religions are like sausages. When you know how they are made, you no longer want them."
    Reply With Quote  
     

  8. #7  
    ▼▼ dn ʎɐʍ sıɥʇ ▼▼ RedPanda's Avatar
    Join Date
    Aug 2012
    Location
    UK
    Posts
    2,737
    Quote 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?
    Last edited by RedPanda; October 14th, 2013 at 04:02 PM.
    SayBigWords.com/say/3FC

    "And, behold, I come quickly;" Revelation 22:12

    "Religions are like sausages. When you know how they are made, you no longer want them."
    Reply With Quote  
     

Similar Threads

  1. what if schwarzchild solution were not exact?
    By logic in forum Astronomy & Cosmology
    Replies: 8
    Last Post: October 9th, 2011, 11:56 AM
  2. I have found the solution to make poverty history
    By Myuncle in forum Philosophy
    Replies: 16
    Last Post: September 14th, 2010, 09:17 AM
  3. Scientists finally found Anti-Aging Solution
    By 60minutes in forum General Discussion
    Replies: 9
    Last Post: July 12th, 2009, 10:11 PM
  4. Complexity of Traveling Salesman Problem
    By diogenes in forum Mathematics
    Replies: 1
    Last Post: May 30th, 2008, 09:27 PM
  5. Complexity of Traveling Salesman Problem
    By diogenes in forum Computer Science
    Replies: 0
    Last Post: May 30th, 2008, 03:27 PM
Tags for this Thread

View Tag Cloud

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •