爬山算法和单对最短路径算法

Question

4

我有一个比较奇怪的问题。有人能告诉我在哪里找到关于使用爬山算法的最短路径算法信息或者简单介绍一下吗？我了解这两个基础知识，但是我无法将它们结合起来。维基百科有一部分内容介绍了如何使用爬山算法解决旅行商问题，但没有提供更详细的说明。

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

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

很抱歉 - 我表达得不太清楚。我知道如何将该想法应用于旅行推销员问题。我想在最短距离算法上使用它。

- pypmannetjies

4个回答

2

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

旅行商问题的一个解决方案是遗传算法，需要：

表示所访问城市的顺序，例如 [纽约，芝加哥，丹佛，盐湖城，旧金山]
适应度函数为旅行距离
选择最佳结果是随机选择物品，取决于其适应度，适应度越高，选择该解决方案存活的概率就越高
突变是将列表中的城市切换，例如 [A，B，C，D] 变成 [A，C，B，D]
交叉两个可能的解决方案 [B，A，C，D] 和 [A，B，D，C] 的结果是 [B，A，D，C]，即将两个列表都从中间切开，并使用一个父母的开头和另一个父母的结尾来形成子代

算法如下：

由于每次执行算法的结果可能不同，因此需要多次执行。

- seb

遗传算法不是爬山算法的一个例子。 - Dario

爬山算法可以被看作是只有一个元素的遗传算法的简单形式。 - seb

因此没有重组。 - Dario

1

我不确定为什么你想要使用爬山算法，因为Djikstra算法是多项式复杂度O(|E|+|V|log|V|)使用斐波那契队列： http://en.wikipedia.org/wiki/Dijkstra的算法

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

但效率的提高取决于具有可接受的启发式估计到目标的距离。 http://en.wikipedia.org/wiki/A*搜索算法

- Larry Watanabe

0

为了攀登TSP，您应该有一个起始路线。当然，选择一个“聪明”的路线也不会有坏处。

从那个起始路线开始，您进行一次更改并比较结果。如果结果更高，则保留新的结果；如果结果更低，则保留旧的结果。重复此过程，直到达到无法再攀登的点，这将成为您的最佳结果。

显然，在TSP中，您很可能会遇到局部最大值。但是，仍然有可能获得不错的结果。

- Onots

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dario · Accepted Answer

你可以随机交换两个城市。

你的初始路径是：A B C D E F A，长度为200。

现在你通过交换C和D来改变它：A B D C E F A，长度为350 - 更糟了！

下一步：A B C D F E A，长度为150 - 你改进了你的解决方案。;-)

爬山算法非常容易实现，但存在局部最大值等问题！[基于相同思想的更好方法是模拟退火。]

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

解决TSP的另一个好的元启发式方法是蚁群优化。