Question

Assume we have a directed weighted connected graph. Vertices represent cities and the edges represent the roads that connect the cities. The idea is to find the quickest path to navigate from city A to city B. Quickest is considered the minimal number of roads to go through. Explain how this could be solved by using hill climbing search heuristic.

Answer 1

Hill climbing search heuristic is mainly used for optimization problems in Artificial Intelligence. It can be used where we wish to maximize or minimize a function by choice of certain input values. We try to find a good solution to the problem which might not be the optimal one.

In the hill climbing approach for solving this problem, we start by selecting a random city. Then, all its successor cities are generated which is obtained by switching the two adjacent cities. The best successor is chosen as per the need and the process is repeated again by selecting best successor as a new state, until we get a satisfactory solution.

Following steps are involved:

1. We determine the initial random path and calculate the distance of this path.

2. We test the paths by swapping the cities.

3. If the initial path is the destination city, we stop. If it is not, we continue with the current state as initial path.

4. The process is repeated until we have found our solution or until we don't we have a new point anymore.

5. If the new state is our destination city, search is stopped. If it is not, but its value is better than now, we make that state into present state. If it is not better, we continue our search.

By following the stated process above, the problem could be solved.