爬山和单对最短路径算法
我有一个有点奇怪的问题。 谁能告诉我在哪里可以找到有关使用爬山方法的最短路径算法的信息，或者给我一些介绍？ 我了解两者的基础知识，但无法将两者放在一起。 维基百科有一个有趣的部分是关于通过爬山来解决旅行推销员的问题，但没有提供更深入的解释如何准确地解决这个问题。
例如，爬山可以是 适用于旅行推销员 问题。 很容易找到解决方案 访问所有城市但将 与最佳状态相比非常差 解决方案。 该算法开始于 这样的解决方案使小 对其进行改进，例如切换 两个城市的顺序 访问过。 最终，一个更好的 已获取路由。
据我了解，您应该选择任何路径，然后迭代它并一路进行优化。 例如，返回并从起始节点选择不同的链接，并检查这是否给出了更短的路径。
抱歉——我没有说清楚。 我了解如何将这个想法应用到旅行推销员身上。 我想在最短距离算法上使用它。
I have a bit of a strange question. Can anyone tell me where to find information about, or give me a little bit of an introduction to using shortest path algorithms that use a hill climbing approach? I understand the basics of both, but I can't put the two together. Wikipedia has an interesting part about solving the Travelling Sales Person with hill climbing, but doesn't provide a more in-depth explanation of how to go about it exactly.
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.
As far as I understand it, you should pick any path and then iterate through it and make optimisations along the way. For instance going back and picking a different link from the starting node and checking whether that gives a shorter path.
I am sorry - I did not make myself very clear. I understand how to apply the idea to Travelling Salesperson. I would like to use it on a shortest distance algorithm.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
你可以随机交换两个城市。
您的第一条路径是：长度为 200 的 ABCDEFA
现在您通过交换 C 和 D 来更改它：长度为 350 的 ABDCEFA - 更糟糕！
下一步：ABCDFEA：长度 150 - 您改进了您的解决方案。 ;-)
爬山算法确实很容易实现，但在局部最大值方面存在一些问题！ [基于相同想法的更好方法是模拟退火。]
爬山是一种非常简单的方法一种进化优化，更复杂的算法类是遗传算法。
解决 TSP 的另一个很好的元启发法是蚁群优化
You could just randomly exchange two cities.
You first path is: A B C D E F A with length 200
Now you change it by swapping C and D: A B D C E F A with length 350 - Worse!
Next step: A B C D F E A: length 150 - You improved your solution. ;-)
Hill climbing algorithms are really easy to implement but have several problems with local maxima! [A better approch based on the same idea is simulated annealing.]
Hill climbing is a very simple kind of evolutionary optimization, a much more sophisticated algorithm class are genetic algorithms.
Another good metaheuristic for solving the TSP is ant colony optimization
例如数据聚类中的遗传算法或期望最大化。 通过单个步骤的迭代，我们试图在每一步中找到更好的解决方案。 问题是它只找到局部最大值/最小值，不能保证找到全局最大值/最小值。
旅行商问题的解决方案作为遗传算法，我们需要：
然后算法：
算法的每次执行结果可能不同，因此应该执行多次。
Examples would be genetic algorithms or expectation maximization in data clustering. With an iteration of single steps it is tried to come to a better solution with every step. The problem is that it only finds a local maximum/minimum, it is never assured that it finds the global maximum/minimum.
A solution for the travelling salesman problem as a genetic algorithm for which we need:
The algorithm then:
It is possible that with every execution of the algorithm the result is differently, therefore it should be executed more then once.
我不确定你为什么要使用爬山算法，因为 Djikstra 的算法是使用斐波那契队列的多项式复杂度 O( | E | + | V | log | 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
I'm not sure why you would want to use a hill-climbing algorithm, since Djikstra's algorithm is polynomial complexity O( | E | + | V | log | V | ) using Fibonacci queues:
http://en.wikipedia.org/wiki/Dijkstra's_algorithm
If you're looking for an heuristic approach to the single-path problem, then you can use A*:
http://en.wikipedia.org/wiki/A*_search_algorithm
but an improvement in efficiency is dependent on having an admissible heuristic estimate of the distance to the goal.
http://en.wikipedia.org/wiki/A*_search_algorithm
要爬 TSP，您应该有一条起始路线。 当然，选择一条“聪明”的路线不会有什么坏处。
从该起始路线开始，您进行一项更改并比较结果。 如果高了就保留新的，如果低了就保留旧的。 重复此操作，直到到达无法再攀爬的点，这将成为您的最佳结果。
显然，使用 TSP，您很可能会达到局部最大值。 但有可能获得不错的结果。
To hillclimb the TSP you should have a starting route. Of course picking a "smart" route wouldn't hurt.
From that starting route you make one change and compare the result. If it's higher you keep the new one, if it's lower keep the old one. Repeat this until you reach a point from where you can't climb anymore, which becomes your best result.
Obviously, with TSP, you will more than likely hit a local maximum. But it is possible to get decent results.