4

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

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

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

对不起-我没有说得很清楚。我了解如何将这个想法应用于旅行推销员。我想在最短距离算法上使用它。

4

4 回答 4

4

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

您的第一条路径是：长度为 200 的 ABCDEFA

现在您通过交换长度为 350 的 C 和 D: ABDCEFA 来更改它 - 更糟！

下一步：ABCDFEA：长度 150 - 您改进了解决方案。;-)

爬山算法真的很容易实现，但是局部最大值有几个问题！[基于相同想法的更好方法是模拟退火。]

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

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

于 2009-05-17T15:56:02.310 回答
2

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

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

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

那么算法：

  • 初始解决方案集的初始化
  • 计算每个解的适应度
  • 直到期望的最大适应度或直到不再发生变化
    • 选择最佳解决方案
    • 交叉和突变
    • 每个解的适应度计算

算法的每次执行结果都可能不同，因此它应该执行一次以上。

于 2009-05-17T16:08:51.953 回答
1

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

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

但是效率的提高取决于对目标距离的可接受的启发式估计。 http://en.wikipedia.org/wiki/A *_search_algorithm

于 2009-06-15T19:38:15.603 回答
0

要爬上 TSP，您应该有一条起始路线。当然，选择“智能”路线不会受到伤害。

从那条起始路线开始，您进行一项更改并比较结果。高了就保留新的，低了就保留旧的。重复此操作，直到您到达无法再攀爬的点，这将成为您的最佳结果。

显然，使用 TSP，您很可能会达到局部最大值。但有可能获得不错的结果。

于 2009-05-17T16:23:42.403 回答