Java：旅行推销员 – 找到多项式算法
编辑 ：找到了对此算法的改进 。 欢迎您来看看。
这个问题是我老问题的改进。 现在我想向您展示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)是输入城市。 用我的PC计算了321550 mills ，（约5分钟）。 Created: 20801457表示Created: 20801457的搜索实例的数量（我使用地图或创建地图的所有时间。您将需要查看代码以更好地理解此数字）。 Map(3)讲述了已创建3个城市的地图数量。 它创建了2448个城市地图并使用了34272次。
我的算法将使用N个城市路线中的K个城市大小生成的地图数量将是：我可以选择我的地图的第一个城市的次数： N乘以我可以选择不同城市选择的次数剩下的城市：（n-1）！ /（（n – k – 1）！*（k-1）！）。 Thas来了！ /（（n – k – 1）！*（k-1）！） 。 假设创建大小为3的地图是primefaces动作，那么我的算法效率将是所有这些地图的总和。
所以我的算法具有下一个效率。
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列几乎相同。 这就是我发现它的方式。
请validation我的工作，看看代码，告诉我你是否同意我。 如果没有，请告诉我我的算法或我的数学不适用于精确样本。 如果您同意我的意见，那么请帮我改变维基页面，通过显示我的算法的这一部分比Held-Karp算法更好。
我会尝试将其分解为必需品。 但首先让我赞扬你解决一个“已知”非常困难的问题。 没有冒险，就无法取得进展。
你正在接近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）的方案。 你不太可能做到这一点，但不要让这挫伤你的热情。
你的工作似乎落在四个关键点上：
- 您似乎不明白多项式时间的含义
- 您的算法似乎无法解决通用的旅行商问题
- 即使您的算法解决的问题是旅行商问题，它也是基于错误的假设，导致它给出错误的答案
- 即使您的算法正确解决了正确的问题，它似乎也不会在多项式时间内运行
对于点1，多项式时间算法不是可以在五分钟内在家用计算机上运行的算法。 术语“多边形时间”，“恒定时间”，“记录时间”等都指算法缩放的方式 。 提供一次运行算法的结果就不会告诉我们这一点。 为了提供算法渐近运行时间的经验数据，您需要对非常大量的随机问题实例进行平均。 例如， 该图提供了以下事实的证据：在两个维度中，用于跨越n个随机点的范围报告的朴素方法是通过朴素方法的O(n^0.5)使用2-d树的O(n^0.5) 。 我解决了10,000个随机生成的问题，分数从2到2 ^（20），我在一些对数尺度上绘制完成时间 – 这些线的梯度为算法的渐近运行时间提供了证据。
一项试验的结果几乎完全没有意义。 如果你不能严格certificate算法是多项式的，那么一组大量的，经过充分分析的经验结果将为你的主张提供证据并让人们感兴趣。 我必须非常重视“大”这个词。
对于第二点，您的算法解决了欧几里德旅行商问题，而不是旅行商问题。 这些是不同的问题。 虽然这种区别是技术性的，并且ETSP仍然是NP难的，但是你没有解决它甚至在关于该主题的任何7个问题中提到它的事实表明你在声称你的解决方案之前没有充分研究该领域。有效。
对于第三点，从我的问题中我可以理解，你的解决方案是基于这样的假设，即通过顶点DEFA的最短哈密顿路径以某种方式与通过顶点EFA的最短哈密顿路径相关。 这是错误的。 假设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是最短路径，并且这种结构可以推广到任意数量的顶点。 知道通过某个顶点子集的最短哈密顿路径告诉您在涉及另一个顶点时的情况。
实际上，从您的一个测试用例中，您的算法已被certificate会产生不正确的结果。 您没有解释在这种情况下发生了什么，也没有说明您是如何解决这个问题。
最后，您给出的和大于二项式系数的 n的和。 看来该网站不支持LaTeX，因此我们将使用(nCk)表示二项式系数n选择k 。 您的总和可以重写为k=1 to n的(k)(nk)(nCk)和。 这个和明显大于k=1 to n的(nCk)之和，所以这个和必须大于2^n ，所以你的算法肯定不是基于你的分析的多项式。 任何涉及一组因子的和将极不可能被certificate是多项式有界的。 如果您需要任何类型的非平凡组合来表示算法的运行时间，它可能不会在多项式时间内执行。
简而言之：您的方法在问题的复杂性方面没有赢得任何好处。
让我们来看看你的方法的复杂性。 您实际上正在做的是计算所有子路径的传递闭包，同时消除在同一城市中开始和结束的每两个子路径的更长时间，以减少下一次迭代的剩余组合的数量。 假设您在散列映射中存储了每对城市之间的距离，因此查找时间在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！） 。