我有一个奇怪的问题。谁能告诉我在哪里可以找到有关使用爬山方法的最短路径算法的信息，或者给我一些介绍？我了解两者的基础知识，但我无法将两者放在一起。维基百科有一个有趣的部分是关于解决旅行销售人员爬山问题，但没有提供更深入的解释，说明如何准确地进行。
For example, hill climbing can be applied to the traveling salesman problem. It is easy to find a solution that visits all the cities but will be very poor compared to the optimal solution. The algorithm starts with such a solution and makes small improvements to it, such as switching the order in which two cities are visited. Eventually, a much better route is obtained.
据我了解，您应该选择任何路径，然后遍历它并在此过程中进行优化。例如返回并从起始节点选择不同的链接并检查是否提供更短的路径。
对不起 - 我没有说清楚。我了解如何将这个想法应用于旅行销售员。我想在最短距离算法上使用它。
最佳答案
你可以随机交换两个城市。
您的第一条路径是: A B C D E F A 长度为 200
现在您通过交换 C 和 D 来更改它:长度为 350 的 A B D C E F A - 更糟!
下一步:A B C D F E A:长度 150 - 您改进了您的解决方案。 ;-)
爬山算法真的很容易实现，但在局部最大值方面有几个问题! [基于相同想法的更好方法是 simulated annealing .]
爬山是一种非常简单的进化优化，更复杂的算法类是genetic algorithms .
解决 TSP 的另一个很好的元启发式方法是 ant colony optimization
关于data-structures - 爬山和单对最短路径算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/874838/