Visualization of Hill Climbing
Hill climbing is one of the Heuristic Search techniques. Hill Climbing
strategies expand the current state in the search and evaluate its children.
The best child is selected for further expansion and neither its siblings
nor its parent are retained. Search halts when it reaches a state that
is better than any of its children. Hill climbing is named for the strategy
that might be used by an eager, but blind mountain climber, go uphill along
the steepest possible path until you can go no further.
Problems in Hill Climbing:
A major problem of hill climbing strategies is their tendency to become
stuck at foothills, a plateau or a ridge. If the algorithm reaches any
of the above mentioned states, then the algorithm fails to
find a solution.
Foothills or local maxima is a state that is better than all its neighbours
but is not better than some other stses farther away. At a local maximum,
all moves appear to make things worse. Foothills are potential traps for
A plateau is a flat area of the search space in which a whole set of neighbouring
ststes have the same value. On a plateau, it i not possible to determine
the best direction in which to move by making local comparisons.
A ridge is a special kind of local maximum. It is an area of the search
space that is higher that the surrounding areas and that itself has a slope.
But theorientation of the high region, compared to the set of available
moves and the directions in which they move, makes it impossible to traverse
a ridge by single moves. Any point on a ridge can look like peak because
movement in all probe directions is downward.
Visualization of Hill Climbing Problems:
A java applet is used to visualize the above mentioned problems in hill
climbing. The back ground of this applet is a hill and this hill is used
for demonstrating the various problems faced in hill climbing search technique.
When the applet is loaded, it shows the hill as a back ground and it also
has a button for each of problems talked above. By clicking the respective
button, the applet shows the search path that will be taken for each of
the above mentioned problems. The search path is represented by a red line.
This red line is obtained by joining all the solution states taken during
the search. The blue lines show possible solution states around the
current state. The green line indicates the best state obtained at each
search point. The green circle at the top of the hill indicates the actual
goal state that is to reached. The start and stop buttons are for starting
and stopping the search. This applet helps the user to visualize and thus
understand the hill climbing search technique and also understand the various
problems faced by hill climbing search technique.