爬山和单对最短路径算法

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.

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

4 个解决方案

#1

You could just randomly exchange two cities.

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

You first path is: A B C D E F A with length 200

您的第一条路径是:A B C D E F A长度为200

Now you change it by swapping C and D: A B D C E F A with length 350 - Worse!

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

Next step: A B C D F E A: length 150 - You improved your solution. ;-)

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

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.]

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

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

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

#2

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:

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

Representation of the solution as order of visited cities, e.g. [New York, Chicago, Denver, Salt Lake City, San Francisco]

将访问城市的顺序表示为解决方案,例如, [纽约,芝加哥,丹佛,盐湖城,旧金山]

Fitness function as the travelled distance

健身功能作为行走距离

Selection of the best results is done by selecting items randomly depending on their fitness, the higher the fitness, the higher the probability that the solution is chosen to survive

通过随机选择项目取决于其适合度来选择最佳结果,适应度越高,选择生存的解决方案的概率越高

Mutation would be switching to cities in a list, like [A,B,C,D] becomes [A,C,B,D]

变异将切换到列表中的城市,如[A,B,C,D]变为[A,C,B,D]

Crossing of two possible solutions [B,A,C,D] and [A,B,D,C] result in [B,A,D,C], i.e. cutting both list in the middle and use the beginning of one parent and the end of the other parent to form the child

交叉两个可能的解[B,A,C,D]和[A,B,D,C]导致[B,A,D,C],即在中间切割两个列表并使用一个父项的开头和另一个父母结束形成孩子

The algorithm then:

然后算法:

initalization of the starting set of solution

初始化解决方案的初始化

calculation of the fitness of every solution

计算每个解的适应度

until desired maximum fitness or until no changes happen any more
- selection of the best solutions
- crossing and mutation
- fitness calculation of every solution

直到期望的最大适应度或直到没有变化发生任何更多选择的最佳解决方案交叉和突变适合度计算每个解决方案

It is possible that with every execution of the algorithm the result is differently, therefore it should be executed more then once.

有可能每次执行算法时结果都不同,因此应该执行一次以上。

#3

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

我不确定你为什么要使用爬山算法,因为Djikstra的算法是使用Fibonacci队列的多项式复杂度O(| E | + | V | log | V |):http://en.wikipedia.org /维基/ 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

如果您正在寻找单路径问题的启发式方法,那么您可以使用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

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

#4

To hillclimb the TSP you should have a starting route. Of course picking a "smart" route wouldn't hurt.

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

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.

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

#1