Geek Answers Handbook

Hill-climbing algorithms and single pairs of the shortest path

I have a strange question. Can someone tell me where to find the information, or give me a little introduction to using the shortest path algorithms that use the hill climbing approach? I understand the basics of both, but I cannot bring them together. Wikipedia has an interesting part on how to allow a Sales Traveler climbing a hill, but does not provide a more detailed explanation of how to do this.

For example, climbing a hill can be applied to a traveling salesman problem. It is easy to find a solution that visits all cities, but it will be very bad compared to the optimal solution. The algorithm begins with such a decision and makes small improvements, such as switching the order in which two cities were visited. In the end, a much better route.

As I understand it, you should choose any path, and then iterate over it and make optimization along the way. For example, go back and select another link from the start node and check if this gives a shorter path.

Sorry, I didn’t say it very clearly. I understand how to apply this idea to Traveling Salesperson. I would like to use it on the shortest distance algorithm.

+4
source share
4 answers

You can just randomly exchange two cities.

You are the first way: ABCDEFA 200

Now you change it, replacing C and D: ABDCEFA 350 long - Worse!

Next step: ABCDFEA: Length 150 - You have improved your solution .; -)

Hill climbing algorithms are really easy to implement, but have a few problems with local maxima! [A more suitable approach based on the same idea is simulated annealing .]

Hill climbing is a very simple type of evolutionary optimization, a much more complex class of algorithms is genetic algorithms .

Another good metaheuristic for TSP solution: ant colony optimization

+4
source

In data clustering, examples would be genetic algorithms or maximizing expectations . With an iteration of single steps, he tries to come up with a better solution with every step. The problem is that it finds only a local maximum / minimum, it never guarantees that it will find a global maximum / minimum.

Solving the traveling salesman problem as a genetic algorithm , for which we need:

  • Presenting a solution as an order of cities visited, for example. [New York, Chicago, Denver, Salt Lake City, San Francisco].
  • Fitness function as distance traveled
  • The selection of the best results is achieved by randomly selecting objects depending on their suitability, the higher the fitness, the higher the likelihood that the solution is chosen for survival.
  • The mutation will switch to cities in the list, for example [A, B, C, D] becomes [A, C, B, D]
  • The intersection of two possible solutions [B, A, C, D] and [A, B, D, C] leads to [B, A, D, C], ie in the middle and use the beginning of one parent and the end of the other parent to form a child

Then the algorithm:

  • initialization of the starting set of solutions
  • calculating the suitability of each solution
  • until maximum suitability is reached or until changes are made
    • choosing the best solutions
    • intersection and mutation
    • suitability calculation for each solution

It is possible that with each execution of the algorithm the result will be different, therefore it should be executed more than once.

+2
source

I'm not sure why you would like to use the hill climbing algorithm, because the Jikstra algorithm is the polynomial complexity O (| E | + | V | log | V |) using Fibonacci queues: http://en.wikipedia.org/wiki / Dijkstra 's_algorithm

If you are looking for a heuristic approach to a single-path problem, you can use A *: http://en.wikipedia.org/wiki/A * _search_algorithm

but an increase in efficiency depends on the availability of a valid heuristic estimate of the distance to the target. http://en.wikipedia.org/wiki/A * _search_algorithm

+1
source

To compress TSP, you must have a start route. Of course, choosing a smart route will not hurt.

From this initial route, you make one change and compare the result. If it is higher, you save the new; if it is lower, keep the old. Repeat this until you reach a point where you can no longer climb, which will be your best result.

Obviously, with TSP, you are most likely to reach a local maximum. But you can achieve decent results.

0
source

More articles:


All Articles