爬山和单对最短路径算法

Question

我有点奇怪的问题。任何人都可以告诉我在哪里可以找到有关信息，或者给我介绍使用最短路径算法使用爬山方法的一些介绍？我理解两者的基础知识，但我不能把两者结合在一起。维基百科有一个有趣的部分，关于如何解决具有爬山问题的旅行销售人员，但没有提供更深入的解释如何完全去做。

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

据我了解，你应该选择任何路径，然后遍历它，并沿途进行优化。例如，返回并从起始节点中选择不同的链接并检查是否给出了较短的路径。

我很抱歉 - 我没有让自己很清楚。我了解如何将这个想法应用到旅行销售人员。我想用最短的距离算法。

Answer 1

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

你先路径为：A B C déF A长度为200

现在你通过交换C和更改d：A B d C ^êF A长度为350 - 更糟！

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

爬山算法真的很容易实现，但有几个本地最大值的问题！ [基于相同想法的更好的方法是simulated annealing。]

爬山是一种非常简单的进化优化，更复杂的算法类是genetic algorithms。

另一个好元启发式用于解决TSP是ant colony optimization

Answer 2

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

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

• 表示所访问城市的顺序，例如[纽约，芝加哥，丹佛，盐湖城，旧金山]
• 健身功能的行驶距离是通过选择项目随机取决于他们的体能做了最好的结果
• 选择越高健身，越高，该溶液被选择为生存
• 突变将被切换到的城市的列表，像[A，B，C，d]变为[A，C，B，d]
概率
• 穿越两种可能的解决方案[B，A，C，D]和[A，B，D， C]结果[B，A，d，C]，即，在中间切割两个列表，然后使用一个父的开始和另一方的端部，以形成子

然后，该算法：

• 起始组的溶液的initalization
• 计算每一个解决方案的健身
• 直到期望的最大健身或直到没有变化发生任何更多
  • 选择最佳的解决方案，交叉和突变适应度计算每一个解决方案的
  • 的

这可能是与算法的每次执行的结果是不同的，因此应执行更然后一次。

Answer 3

要登上TSP，你应该有一条出发路线。当然，选择一条“智能”路线不会有什么影响。

从该起始路线中，您进行一项更改并比较结果。如果它更高，则保留新的，否则保留旧的。重复这个步骤，直到你到达一个你不能爬的地步，这将成为你最好的结果。

显然，使用TSP时，您可能会达到当地最大值。但有可能获得体面的结果。

Answer 4

我不知道你为什么会想使用爬山算法，因为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