Java: Traveling Salesman - Found polynomial algori

问题:

Edit: An improvement to this algorithm been found. Your are welcome to see it.

This question is the an improvement of my old question. Now I want to show you Java code sample, and explain my algorithm in more details.

I think that I found a polynomial algorithm to get an exact solution to the Traveling Salesman Problem. My implementation is build from 5 steps:

• 1) Quick setup
• 2) Search for solution
• 3) Stop condition 1
• 4) Stop condition 2
• 5) Stop condition 3

I want to start from step 2 and 3, and if I do not get wrong there I will show you the rest of it.

So what I am going to show you now, is not polynomial algorithm, but an improvement to Held–Karp algorithm that solves the problem in time O(n^2 2^n)

Lets say we want to solve a 6 cities route with the brout algorithm. There are (6-1)! = 120 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 120

Now I am saying that after calculating option 1 and 2, you can skip over 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, it actually calculating options 1 and 2. What we want to do is to build a map of 4 cities where we force what would be the first and the last city, in this example when calculating option 1 you create a map of D,E,F,A that holds the data of what would be the shortest path from D to A thru E,F. So now 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. This is just one sample but it have a bigger meaning than that. In fact it represent all the results for 19 cities. No matter what 19 cities input will it be, the algorithm will always create the same amount of maps, perform the same amount of actions and will resolve with the same time.

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 search instances created(all the times that I used map or created the map. You will need to see the code to understand this number better). 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.

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

So what kind of efficiency is this?

It looks like exponential function of O(N^C*2^N) where C is just a bit smaller than one. I found this by solving the efficiency 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) and I find 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.

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 

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. If you agree with me, then help me to change the wiki page by showing that this part of my algorithm is better then Held–Karp algorithm.

回答1:

I'll try to break this down to essentials. But first let me commend you for tackling a problem that's "known" to be enormously hard. No progress can be made without risk taking.

You are approaching TSP in terms of a recursive expression for S(a, b, I), the length of a shortest path from city a to city b, a \ne b, passing through each city in the unordered set I exactly once.

With S in hand, the TSP is easy to solve. For the set of cities C, find

min( D(b, a) + S(a, b, C\a\b) ) over all pairs a, b drawn from C where a \ne b

Here D(x, y) = D(y, x) is the distance from city x to y and C\a\b is C with a and b removed.

The recursive expression you propose for S is

S(a, b, I) = min( D(a, p) + S(p, q, I\p\q) + D(q, b) ) 
               over all pairs p, q drawn from I where p \ne q ,  

The base cases are where I has zero or one element(s). These are pretty obvious.

You are proposing to cache values of S(a, b, I) so that no such computation is ever repeated. (This is called memoizing by the way.)

So what is the cost of this computation, or equivalently the size of the cache? We can write a recurrence for it, where the parameter n = |I| is the number of cities in the intermediate set:

C(n) = M(n, 2) C(n - 2) = ( n(n-1)/2 )  C(n - 2)
C(0) = C(1) = 1

Here M(n, m) is the combination of n things taken m at a time, n! / (m! (n-m)!)

We can solve this. For even n:

C(n) = n! /  2^(n/2)

I'll let you work out the odd case.

For the tour among m cities, we'd need to repeat this for all city pairs and corresponding intermediate sets:

(m(m-1)/2) C(m-2) = m! / 2^(m/2-2)

So your method does avoid an exponential amount of work with respect to the naïve algorithm of generating all possible tours, but the factorial still dominates: this function is super-exponential.

NB on your other "stopping criteria:" Above is the cost of computing all possible values of S(a,b,I) exactly once. To get a poly time algorithm, you will have to come up with a scheme for skipping a super-exponential number (a,b,I) of triples entirely. It's unlikely you can do this, but don't let this dampen your enthusiasm.

回答2:

Your work seems to fall down on four key points:

1. You do not seem to understand what Polynomial Time means
2. Your algorithm does not appear to solve the generic Travelling Salesman Problem
3. Even if the problem your algorithm solves is the Travelling Salesman Problem, it is predicated on a false assumption, causing it to give wrong answers
4. Even if your algorithm correctly solved the correct problem, it does not appear to run in polynomial time

For point 1, a polynomial time algorithm is not one which can be run on a home computer in five minutes. The terms "poly time", "constant time", "log time", etc all refer to the manner in which an algorithm scales. Providing the results from one run of the algorithm tells us nothing about this. In order to provide empirical data on the asymptotic running time of your algorithm, you will need to average over a very large number of random problem instances. For instance, this graph gives evidence for the fact that, in two dimensions, a naive method for range reporting across n random points is O(n) by the naive method and O(n^0.5) using a 2-d tree. I solved 10,000 randomly generated problems for numbers of points ranging from 2 to 2^(20) and I plotted the completion times on some log scales - the gradients of these lines gives evidence for the asymptotic running times of the algorithms.

The results of one trial are almost completely meaningless. If you cannot rigorously prove that an algorithm is polynomial then a large, well analysed set of empirical results, will give evidence for your claim and get people interested. I must place great emphasis on the word "large".

For the second point, your algorithm solves the Euclidean Travelling Salesman Problem, and not the Travelling Salesman Problem. These are different sets of problems. Though this distinction is technical and the ETSP is still NP-hard, the fact that you have not addressed it or even mentioned it in any of your 7 questions on the topic suggests that you haven't adequately researched the field before claiming your solution is valid.

For the third point, from what I can understand from your question, your solution is predicated on the assumption that the shortest Hamiltonian path through vertices D E F A is somehow related to the shortest Hamiltonian path through vertices E F A. This is false. Suppose that E->F->A is the shortest path through those vertices. If D is close to E and chosen such that DEF are colinear with vertices appearing in that order, then the shortest path is D->E->F->A. If D is chosen to be halfway along the line between E and F, the shortest path is E->D->F->A. Similar choices to before can give us vertex arrangements such that E->F->D->A and E->F->A->D are the shortest paths, and such a construction can generalise to any number of vertices. Knowing the shortest Hamiltonian path through some subset of vertices tells you nothing about the situation when another vertex gets involved.

Indeed, from one of your test cases, your algorithm has been shown to produce incorrect results. You have given no explanation as to what happened in this case, nor any indication of how or even if you have fixed this problem.

Finally, the sum you have given is greater than the sum to n of the binomial coefficients. It seems that LaTeX is not supported on this site, so we'll use (nCk) to denote the binomial coefficient n choose k. Your sum can be re-written as the sum of (k)(n-k)(nCk) for k=1 to n. This sum is clearly greater than the sum of (nCk) for k=1 to n, so this sum must be greater than 2^n, so your algorithm is certainly not polynomial based on your analysis. It is highly unlikely that any sum involving a bunch of factorials will turn out to be polynomially bounded. If you require any kind of non-trivial combinatorics to express your algorithm's run time, it probably does not execute in polynomial time.

回答3:

In short: Your approach won nothing in terms of complexity of the problem.

Let's look at the complexity of your approach. What you are effectively doing is calculating the transitive closure of all subpaths, while eliminating the longer from every two subpaths that start and end in the same city, to reduce the number of remaining combinations for the next iteration. Let's assume you stored the distances between every pair of cities in a hashmap, so lookup time is in O(1).

Given that you have n cities you want to include in you route, there are n x (n-1) pairs.

To calculate the distances for all subpaths of length 3, you chose one city and combine it with every pair that does not itself include the chosen city. There are (n-1) x (n-2) such pairs. As you have *n) cities to chose for the first position, you have 3 x 2 x 1 paths of length 3 to calculate. For n = 3 that means you have O(n!).

To calculate the distances for all subpaths of length 4, you repeat the process. This time you need 4 x 3 x 2 x 1 calculations. For n = 4 that means you have O(n!). This is the point where your elimination starts its effect. From every two paths that start and end in the same cities, you only need to remember the shorter one. This means that only (4 x 3 x 2 x 1)/2 paths of length 4 remain.

To calculate the distances for all subpaths of length 5, you gain from the elimination done in the last step. You need to calculate only 5 x (4 x 3 x 2 x 1)/2. For n = 5 that means you have O(1/2 x n!) = O(n!). This time you can eliminate 5 out of the 6 paths that start and end in the same cities (some of which you didn't even calculate, because of the elimination in the previous step), leaving you with (5 x 4 x 3 x 2 x 1)/6 paths of length 5.

Consequentially, for n = 6 you have O(1/6 x n!), which is still O(n!). For every further step the factor will become smaller. What means that you algorithm is faster than the naive brute force approach that does not save any intermediate results. But your complexity remains O(n!).