Java：旅行推销员 - 找到多项式算法 [英] Java: Traveling Salesman - Found polynomial algorithm

问题描述

编辑：改进到这个算法被发现。你可以看到它。

这个问题是对我的改进老问题。现在我想向您展示 Java代码示例，并解释我的算法我想我找到了一个多项式算法来得到旅行推销员问题的一个精确的解决方案。我的实施是从5个步骤构建的：

• 1）快速设置


• 2）搜索解决方案


• 3）停止条件1


• 4）停止条件2


• 5）停止条件3

我想从步骤2和步骤3开始，如果没有我会告诉你其余的。

所以现在我要告诉你，不是多项式算法，但是改进 Held-Karp算法，以及时解决问题O（n ^ 2 2 ^ n）

假设我们想用brout算法解决6个城市的路线。有（6-1）！ = 120 选项，我们需要测试它们并返回创建的最短路线。所以它会看起来像这样（城市名称是：A，B，C，D，E，F）：选项1： A→B→C→D→E→F→A 选项2：A→B→C→D→F <选项3：A - > C - > B - > > - > D - > E - > F - > A

选项4：A - > C - > B D - > F - > E - > A

。

li>

选项120

现在我说在计算选项1和2，你可以跳过选项3和4.你怎么做？很简单：在计算选项1时，您需要计算从D城市开始的最短路线，在城市A完成，并通过城市E，F实际计算选项1和2.我们要做的是建立一个4个城市的地图，在这个城市中，我们强迫什么是第一个和最后一个城市，在这个例子中，当计算选项1时，您创建了一个D，E，F，A的地图， D到A到E，F。所以现在当你开始计算选项3和4时，你可以在到达城市D时停下来，因为你已经知道从D城市开始的最短路线，在城市A完成并穿过城市E，F。

b
$ b

这是我在我的算法中使用的原理。我运行一个暴力算法并映射所有子结果，这些结果不是子路径，不要在那里混淆。它们只是为了找到最短路线而需要完成的计算的一部分。因此，每次我认识到我正在做同样的计算时，我使用了地图上的解决方案。

这是我的算法在19个城市运行的输出。这只是一个样本，但它的含义比这更大。实际上它代表了19个城市的所有结果。无论19个城市的输入是什么，该算法将始终创建相同数量的地图，执行相同数量的动作并在同一时间解决。

<$ p （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]
完成Map 321550磨后的发动机试验
创建时间：20801457
地图（3）写作2448阅读34272
地图（4）写12240阅读159120
地图（5）写42840阅读514080
地图（6） ）写111384阅读1225224
地图（7）写222768阅读2227680
地图（8）写350064阅读3150576
地图（9）写437580阅读3500640
地图（10）写437580阅读3084270
地图（11）写352185阅读2344256
地图（12）说明245131阅读1382525
地图（13）Wri te 135638阅读570522
地图（14）写54320阅读156758
地图（15）写15077阅读27058
地图（16）写2809阅读2087
地图（17）阅读0
地图（18）写18阅读0
地图（19）写1阅读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]

来源（19）是输入的城市。用我的电脑 321550工厂来计算（大约5分钟）。 创建时间：20801457 表示创建的搜索实例的数量（我用来映射或创建地图的所有时间，您需要查看代码才能更好地理解此数字）。 地图（3）说明已创建3个城市的地图数量。它创建了2448个3个城市的地图，并使用它们34272次。

我的算法将生成的地图数量与K个城市在N个城市路线中的尺寸一致：次数我可以选择我的地图中的第一个城市： N 乘以我可以从其余城市选择不同城市的次数：（n-1）！ /（（n-k-1）！*（k-1）！）。 Thas来到 n！ /（（n-k-1）！*（k-1）！）。假设创建一个大小为3的地图是一个原子动作，那么我的算法效率将是所有这些地图的总和。

所以我的算法具有下一个效率。 / h2>

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

那么这是一种什么样的效率呢？

O（N ^ C * 2 ^ N）的指数函数，其中C只比一个小一点。我通过求解效率算法找到了这个结果，N从7到100，并将其与之前的结果（N = 8的结果N = 8，N = 24的结果N = 23）相比较，我发现对于大数N的比较结果是2.然后我就做了和传统动态编程算法一样的效率。这里列出了我得到的结果：

第1列是N，第2列是我的算法效率比较，第3列是动态规划算法比较，第4列是我的算法效率乘以N比较。

  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 $ b $ 12 2.19258 2.38016 2.39191 
 13 2.17251 2.34722 2.35356 $ b $ 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 
 2.10533 2.21606 2.21614 $ b $ 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 $ b $ 27 27 2.07692 2.1568 2.1568 
 28 2.07407 2.15089 2.15089 $ b $ 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 $ b $ 34 2.0606 2.12304 2.12304 
 35 2.05882 2.11937 2.11937 $ b $ 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 
 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 
 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.05 673 
 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 
 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 
 2.0204 2.04102 2.04102 
 2.0202 2.0406 2.0406 
  

看看第3列和第4列几乎是一样的。这是我发现它的方式。

请验证我的工作，看看代码，告诉我你是否同意我的观点。如果不是，请让我看看我的算法或我的数学算法在哪些地方无法用精确的样本工作。如果你同意我的观点，那么通过显示我的算法的这一部分比Held-Karp算法更好，帮助我更改wiki页面。

解决方案

我会尽力将其分解为基本要素。但首先让我赞扬你解决一个已知的问题非常困难。没有冒险就无法取得进展。

您正在以S（a，b，I）的递归表达式接近TSP，即最短路径从城市a到城市b，在无序集合中穿过每个城市我只有一次。

使用S，TSP很容易解决。对于一组城市C，找到

  min（D（b，a）+ S（a，b，C \ a \\ b））在所有对a，b从C中绘出，其中a \\ bne b $ b  

这里D（x，y）= D（y，x）是从城市x到y的距离，C \\\\b是去掉了a和b的C。

你为S提出的递归表达式是：

$ p code $ S（a，b，I）= min（D（a， p）+ S（p，q，I \ p \ q）+ D（q，b））
在所有对p中，q从I中抽取其中p \ q，

基本情况是我有零个或一个元素的地方。这些都非常明显。

您建议缓存S（a，b，I）的值，以免重复执行此类计算。 （这就是所谓的记忆。）

那么这个计算的成本是多少，或者等价于缓存的大小？我们可以为它写一个循环，其中参数n = | I |是中间集合中的城市数量：

pre code> C（n）= M（n，2）C（n - 2 ）=（n（n-1）/ 2）C（n-2）
C（0）= C（1）= 1

这里M（n，m）是一次取n个事物的组合，n！ /（m！（n-m）！）

我们可以解决这个问题。甚至是n：

  C（n）= n！ / 2 ^（n / 2）
  

我会让你解决奇怪的情况。

对于m个城市之间的旅行，我们需要为所有城市对和相应的中间套餐重复此操作：

 （m（m-1）/ 2）C（m-2）= m！ / 2 ^（m / 2-2）
  

所以你的方法确实避免了指数级的工作尊重生成所有可能巡视的朴素算法，但因子依然占主导地位：这个函数是超指数的。

注意你的其他停止标准：以上是计算S（a，b，I）所有可能值的成本。为了得到一个多时间算法，你将不得不提出一个完全跳过三元组超级指数（a，b，I）的方案。你不可能这样做，但不要让这抑制你的热情。

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.

解决方案

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.

这篇关于Java：旅行推销员 - 找到多项式算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！