编辑:发现了对该算法的改进。欢迎你来看看。
这个问题是对我的老问题的改进。现在我想向您展示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 算法更好。