Hill Climbing Procedure

This is a variety of depth-first (generate - and - test) search. A feedback is used here to decide on the direction of motion in the search space. In the depth-first search, the test function will merely accept or reject a solution. But in hill climbing the test function is provided with a heuristic function which provides an estimate of how close a given state is to goal state. The hill climbing test procedure is as follows :

1. General he first proposed solution as done in depth-first procedure. See if it is a solution. If so quit , else continue.

2. From this solution generate new set of solutions use , some application rules

3. For each element of this set

   (i) Apply test function. It is a solution quit.

   (ii) Else see whether it is closer to the goal state than the solution already generated. If yes, remember it else discard it.

4. Take the best element so far generated and use it as the next proposed solution. This step corresponds to move through the problem space in the direction Towards the goal state.

5.Go back to step 2.

Sometimes this procedure may lead to a position, which is not a solution, but from which there is no move that improves things. This will happen if we have reached one of the following three states.

   (a) A "local maximum " which is a state better than all its neighbors , but is not better than some other states farther away. Local maxim sometimes occur with insight of a solution. In such cases they are called " Foothills".

   (b) A "plateau" which is a flat area of the search space, in which neighboring states have the same value. On a plateau, it is not possible to determine the best direction in which to move by making local comparisons.

   (c) A "ridge" which is an area in the search that is higher than the surrounding areas, but can not be searched in a simple move.

To overcome theses problems we can

   (a) Back track to some earlier nodes and try a different direction. This is a good way of dealing with local maxim.

   (b) Make a big jump an some direction to a new area in the search. This can be done by applying two more rules of the same rule several times, before testing. This is a good strategy is dealing with plate and ridges.

Hill climbing becomes inefficient in large problem spaces, and when combinatorial explosion occurs. But it is a useful when combined with other methods.