Ily*_*man -9 java graph np-complete traveling-salesman np-hard
编辑:找到了对此算法的改进.欢迎您来看看.
这个问题是我老问题的改进.现在我想向您展示Java代码示例,并更详细地解释我的算法.
我认为我找到了一个多项式算法来获得旅行商问题的精确解.我的实现是从5个步骤构建的:
我想从第2步和第3步开始,如果我没有错,我会告诉你其余部分.
所以我现在要向您展示的不是多项式算法,而是对Held-Karp算法的改进,它解决了时间问题O(n ^ 2 2 ^ n)
让我们说我们想用brout算法解决6个城市的路线.有(6-1)!= 120选项,我们需要测试它们并返回最短的路线.所以它看起来像那样(城市名称是:A,B,C,D,E,F):
现在我说在计算选项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个城市地图并使用了34272次.
我的算法将在N个城市路线中使用K个城市大小生成的地图数量将是:我可以选择我的地图的第一个城市的次数:N乘以我可以选择不同城市选择的次数剩下的城市:(n-1)!/((n - k - 1)!*(k-1)!).Thas来了!/((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略小于1.我通过求解效率算法找到了这个,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列几乎是一样的.这就是我发现它的方式.
请验证我的工作,看看代码,告诉我你是否同意我.如果没有,请告诉我我的算法或我的数学不适用于精确样本.如果您同意我的意见,请通过显示我的算法的这一部分比Held-Karp算法更好来帮助我更改维基页面.
ymb*_*rtt 26
你的工作似乎落在四个关键点上:
对于点1,多项式时间算法不是可以在五分钟内在家用计算机上运行的算法.术语"多边形时间","恒定时间","记录时间"等都是指算法缩放的方式.提供一次运行算法的结果就不会告诉我们这一点.为了提供算法的渐近运行时间的经验数据,您需要对非常大量的随机问题实例进行平均.例如,这个图表证明了这样一个事实,即在两个维度上,n个随机点的范围报告O(n)的朴素方法是通过朴素的方法和O(n^0.5)使用二维树.我解决了10,000个随机生成的问题,分数从2到2 ^(20),我在一些对数尺度上绘制了完成时间 - 这些线的梯度为算法的渐近运行时间提供了证据.
一次试验的结果几乎完全没有意义.如果你不能严格证明一个算法是多项式的,那么一组大量的,经过充分分析的经验结果将为你的主张提供证据并让人们感兴趣.我必须非常重视"大"这个词.
对于第二点,您的算法解决了欧几里德旅行商问题,而不是旅行商问题.这些是不同的问题.虽然这种区别是技术性的,并且ETSP仍然是NP难的,但是你没有解决它甚至在关于该主题的任何7个问题中提到它的事实表明你在声称你的解决方案之前没有充分研究该领域.有效.
对于第三点,从我的问题可以理解,你的解决方案是基于通过顶点的最短哈密顿路径D E F A以某种方式与通过顶点的最短哈密顿路径相关的假设E F A.这是错误的.假设这E->F->A是通过这些顶点的最短路径.如果D接近E并选择DEF为具有以该顺序出现的顶点的共线,则最短路径为D->E->F->A.如果D选择在E和之间的线的中间F,则最短的路径是E->D->F->A.之前的类似选择可以给我们这样的顶点排列E->F->D->A和E->F->A->D是最短路径,这种结构可以推广到任意数量的顶点.知道通过顶点的一些子集的最短哈密顿路径告诉你在涉及另一个顶点时的情况.
实际上,从您的一个测试用例中,您的算法已被证明会产生不正确的结果.您没有解释在这种情况下发生了什么,也没有说明您是如何解决这个问题.
最后,您给出的和大于二项式系数的 n的和.看来该网站不支持LaTeX,因此我们将(nCk)用来表示n选择二项式系数k.您的总和可以重写为(k)(n-k)(nCk)for 的总和k=1 to n.这个总和显然大于(nCk)for 的总和k=1 to n,所以这个总和必须大于2^n,所以你的算法肯定不是基于你的分析的多项式.涉及一堆因子的任何和将极不可能被证明是多项式有界的.如果您需要任何类型的非平凡组合来表示算法的运行时间,它可能不会在多项式时间内执行.
Gen*_*ene 10
我会尝试将其分解为必需品.但首先让我赞扬你解决一个"已知"非常困难的问题.没有冒险,就无法取得进展.
你正在接近TSP的S(a,b,I)的递归表达式,从城市a到城市b的最短路径的长度,一个\ne b,在无序集合中穿过每个城市我只有一次.
有了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是C,其中a和b被移除.
你为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)是一次取m个n的组合,n!/(m!(nm)!)
我们可以解决这个问题 对于偶数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)的方案.你不太可能做到这一点,但不要让这挫伤你的热情.
| 归档时间： |
|
| 查看次数： |
5247 次 |
| 最近记录： |