Hill climbing and single-pair shortest path algorithms

Question

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 optimizations 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 of Travelling Salesperson. I would like to use it in the shortest distance algorithm.

Answer 1

The problem of finding the shortest path between a pair of nodes has various applications in the field of engineering and science. For the past years, researchers have not only developed effective solutions but also have given efficient algorithms to solve these problems. The developments in the field of artificial intelligence have drawn the attention of many researchers in modeling problems involving searches. The shortest path problem, as we know, tries to search the best next node in the process of reaching the goal node.

Since it involves searching and in the large problem domain, one might make use of heuristic searching techniques for the same A* heuristic search technique can be used to solve this problem effectively. In this case, it makes use of simple calculation of estimated cost value f as a function of g and h; where f=g+h. Where g(n), represents the cost of choosing the path from starting node to node n; and h(n) represents the optimal cost of node n to the goal node.

Hill climbing algorithms are easy to implement but have many problems with local maxima. [A better approach based on the same idea is simulated annealing.]

Hill climbing is a very simple kind of evolutionary optimization, a much more sophisticated algorithm class is genetic algorithms.

Another good metaheuristic for solving the TSP is ant colony optimization.