java - Java：旅行推销员 - 找到多项式算法

Question

编辑：发现了对该算法的改进。欢迎你来看看。

这个问题是对我的老问题的改进。现在我想向您展示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 -> E -> A
• 选项 3：A -> C -> B -> D -> E -> F -> A
• 选项 4：A -> C -> B -> D -> F -> E -> A
• .
• .
• 选项 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 市的最短路线。

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

这是我的算法在 19 个城市上运行的输出。这只是一个样本，但它的意义远不止于此。事实上，它代表了 19 个城市的所有结果。无论 19 个城市的输入是什么，算法总是会创建相同数量的地图，执行相同数量的操作，并且会在相同的时间内解决。

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)是输入城市。我的电脑321550 mills计算了一下，（大约 5 分钟）。Created: 20801457表示创建的搜索实例的数量（我使用地图或创建地图的所有时间。您需要查看代码才能更好地理解这个数字）。Map(3)谈到已创建的 3 个城市的地图数量。创建了2448张3城地图，使用了34272次。

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

所以我的算法有下一个效率。

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 比 one 小一点。我通过求解效率算法找到了这一点，N 从 7 到 100，并将其与之前的结果（N = 9 和 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 
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 

看看第 3 列和第 4 列是如何几乎相同的。我就是这样找到它的。

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

Answer 1

你的工作似乎落在四个关键点上：

1. 您似乎不明白多项式时间的含义
2. 您的算法似乎无法解决通用的旅行商问题
3. 即使你的算法解决的问题是旅行商问题，它也是基于错误的假设，导致它给出错误的答案
4. 即使您的算法正确解决了正确的问题，它似乎也不会在多项式时间内运行

对于第 1 点，多项式时间算法不是可以在五分钟内在家用计算机上运行的算法。术语“poly time”、“constant time”、“log time”等都是指算法缩放的方式。提供一次算法运行的结果并没有告诉我们任何关于这一点的信息。为了提供算法渐近运行时间的经验数据，您需要对大量随机问题实例进行平均。例如，该图提供了以下事实的证据：在二维中，用于跨 n 个随机点的范围报告O(n)的简单方法是通过简单方法和O(n^0.5)使用二维树。我解决了 10,000 个随机生成的问题，点的数量从 2 到 2^(20) 不等，我在一些对数尺度上绘制了完成时间——这些线的梯度为算法的渐近运行时间提供了证据。

一项试验的结果几乎毫无意义。如果你不能严格证明一个算法是多项式的，那么一组经过充分分析的经验结果将为你的主张提供证据并引起人们的兴趣。我必须非常强调“大”这个词。

对于第二点，您的算法解决了欧几里得旅行商问题，而不是旅行商问题。这些是不同的问题。尽管这种区别是技术性的，并且 ETSP 仍然是 NP-hard，但您在关于该主题的 7 个问题中的任何一个问题中都没有解决甚至提到它，这表明您在声称您的解决方案之前没有充分研究该领域是有效的。

对于第三点，根据我从您的问题中可以理解的情况，您的解决方案基于这样的假设，即通过 vertices 的最短哈密顿路径与通过 vertices 的最短哈密顿路径D E F A有某种关系E F A。这是错误的。假设这E->F->A是通过这些顶点的最短路径。如果D接近E并选择了DEF与以该顺序出现的顶点共线，则最短路径为D->E->F->A。如果选择在和D之间的中途，则最短路径为。与之前类似的选择可以给我们顶点排列，这样和EFE->D->F->AE->F->D->AE->F->A->D是最短路径，这样的构造可以推广到任意数量的顶点。知道通过某些顶点子集的最短哈密顿路径不会告诉您涉及另一个顶点时的情况。

事实上，从您的一个测试用例中，您的算法已被证明会产生不正确的结果。你没有解释在这种情况下发生了什么，也没有说明你是如何解决这个问题的，或者你是否已经解决了这个问题。

最后，您给出的总和大于二项式系数n 的总和。这个站点似乎不支持 LaTeX，所以我们将使用选择(nCk)来表示二项式系数。您的总和可以重写为for的总和。这个总和显然大于for的总和，所以这个总和必须大于，所以根据您的分析，您的算法肯定不是多项式。任何涉及一堆阶乘的总和都不太可能是多项式有界的。如果您需要任何类型的非平凡组合来表达您的算法的运行时间，它可能不会在多项式时间内执行。nk(k)(n-k)(nCk)k=1 to n(nCk)k=1 to n2^n

Answer 2

我将尝试将其分解为基本要素。但首先让我赞扬你解决了一个“已知”非常困难的问题。不冒险就不可能取得进展。

您正在根据 S(a, b, I) 的递归表达式来接近 TSP，这是从城市 a 到城市 b 的最短路径的长度，a \ne b，恰好经过无序集 I 中的每个城市一次。

有了S，TSP就很容易解决了。对于城市集 C，求

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

这里 D(x, y) = D(y, x) 是城市 x 到 y 的距离，C\a\b 是去掉 a 和 b 的 C。

您为 S 提出的递归表达式是

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 ,  

基本情况是我有零个或一个元素。这些都很明显。

您建议缓存 S(a, b, I) 的值，以便不再重复此类计算。（顺便说一下，这被称为记忆。）

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

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

这里 M(n, m) 是 n 次取 m 的东西的组合，n！/（米！（纳米）！）

我们可以解决这个问题。对于偶数 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) 的方案。你不太可能做到这一点，但不要让这削弱你的热情。

Answer 3

简而言之：就问题的复杂性而言，您的方法一无所获。

让我们看看您的方法的复杂性。您实际上正在做的是计算所有子路径的传递闭包，同时消除在同一城市开始和结束的每两个子路径中较长的部分，以减少下一次迭代的剩余组合数量。假设您将每对城市之间的距离存储在哈希图中，因此查找时间在O(1)中。

假设您有n个城市要包含在您的路线中，则有nx (n-1)对。

要计算长度为 3 的所有子路径的距离，您选择了一个城市并将其与本身不包含所选城市的每一对组合。有(n-1) x (n-2) 个这样的对。由于您有 *n) 个城市可供选择作为第一个位置，因此您需要计算3 x 2 x 1条长度为 3 的路径。对于n = 3这意味着你有O(n!)。

要计算所有长度为 4 的子路径的距离，请重复该过程。这次您需要4 x 3 x 2 x 1的计算。对于n = 4这意味着你有O(n!)。这是您的消除开始发挥作用的地方。从同一城市开始和结束的每两条路径中，您只需要记住较短的一条。这意味着只剩下(4 x 3 x 2 x 1)/2条长度为 4 的路径。

要计算所有长度为 5 的子路径的距离，您可以从最后一步中的消除中获益。您只需要计算5 x (4 x 3 x 2 x 1)/2。对于n = 5，这意味着您有O(1/2 xn!) = O(n!)。这次您可以消除 6 条路径中的 5 条，起点和终点在同一城市（其中一些您甚至没有计算，因为上一步中已消除），剩下(5 x 4 x 3 x 2 x 1)/6条长度为 5 的路径。

因此，对于n = 6你有O(1/6 xn!)，它仍然是O(n!)。对于每进一步的步骤，该因子将变得更小。这意味着您的算法比不保存任何中间结果的天真蛮力方法更快。但是您的复杂性仍然是O(n!)。