Computer Science Canada Found exact solution for TSP |
| Author: | ilya.gazman [ Sun Oct 13, 2013 11:59 am ] | ||||
| Post subject: | Found exact solution for TSP | ||||
Hi, My name is Ilya Gazman. I found an exact solution for Traveling salesmen problem. Currently the best implementation according to [url="https://en.wikipedia.org/wiki/Travelling_salesman_problem#Exact_algorithms"]wiki[/url] 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) 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:
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. |
|||||
| Author: | Tony [ Sun Oct 13, 2013 1:07 pm ] |
| Post subject: | RE:Found exact solution for TSP |
According to that wikipedia page, the current best exact algorithm is Concorde TSP Solver, although it doesn't cite algorithm's runtime complexity. Held?Karp algorithm is just an example of "One of the earliest applications of dynamic programming" to this domain. |
|