爬山和单对最短路径算法

题

我有一个有点奇怪的问题。谁能告诉我在哪里可以找到有关使用爬山方法的最短路径算法的信息，或者给我一些介绍？我了解两者的基础知识，但无法将两者放在一起。维基百科有一个有趣的部分是关于通过爬山来解决旅行推销员的问题，但没有提供更深入的解释如何准确地解决这个问题。

例如，攀岩可以应用于旅行推销员问题。很容易找到一个访问所有城市的解决方案，但与最佳解决方案相比，它非常差。该算法从这样的解决方案开始，并对其进行了较小的改进，例如切换访问两个城市的顺序。最终，获得了更好的路线。

据我了解，您应该选择任何路径，然后迭代它并一路进行优化。例如，返回并从起始节点选择不同的链接，并检查这是否给出了更短的路径。

抱歉——我没有说清楚。我了解如何将这个想法应用到旅行推销员身上。我想在最短距离算法上使用它。

解决方案

您可能只是随机交换两个城市。

您第一路径是：A B C déF A与长度200

现在你通过交换C和d改变它：A B dÇéF A与长度350 - 更糟

下一步：A B C d˚FE中：长度150 - 你经过改进的解决方案。 ; - ）

爬山算法是很容易实现，但有几个问题与当地极大！ [基于相同的想法更好的计算策略是模拟退火。]

爬山是一个非常简单的一种进化优化的，一个更复杂的算法是类遗传算法

另一个好元启发式用于解决TSP是蚁群

其他提示

例子是 遗传算法 或者 期望最大化 在数据聚类中。通过单个步骤的迭代，我们试图在每一步中找到更好的解决方案。问题是它只找到局部最大值/最小值，不能保证找到全局最大值/最小值。

旅行商问题的解决方案 遗传算法 为此我们需要：

表示解决方案按访问城市的顺序排列，例如[纽约、芝加哥、丹佛、盐湖城、旧金山]
健身功能 作为行驶距离
选择最好的结果是通过根据适应度随机选择项目来完成的，适应度越高，选择解决方案生存的概率就越高
突变将切换到列表中的城市，例如 [A,B,C,D] 变为 [A,C,B,D]
穿越两个可能的解决方案 [B,A,C,D] 和 [A,B,D,C] 的结果为 [B,A,D,C]，即从中间切割两个列表，并使用一个父级的开头和另一个父级的结尾来形成子级

那么算法：

算法的每次执行结果可能不同，因此应该执行多次。

我不知道你为什么会想使用爬山算法，因为Djikstra的算法是多项式复杂度为O（| E | + | V |登录| V |）使用斐波那契队列： http://en.wikipedia.org/wiki/Dijkstra 's_algorithm

如果你正在寻找一个启发式算法单路径问题，那么你可以使用A *： http://en.wikipedia.org/wiki/A * _search_algorithm

但效率的提高依赖于具有与目标的距离的容许的启发式估计。 http://en.wikipedia.org/wiki/A * _search_algorithm

要hillclimb你应该有一个启动路线TSP。当然，选择一个“聪明”的路线不会受到伤害。

这是开始的路线你做一个变化，并将结果进行比较。如果是你高保持新的，如果它是保持较低的旧的。直到你到达那里你可以不爬了，成为你最好的结果的点重复这一点。

显然，TSP，你将很可能在本地最大的打击。但它有可能获得不错的结果。

许可以下： CC-BY-SA 和归因