The Hill – climbing search algo is shown in figure 4.11. it is simply a loop that continuously moves in the direction of increasing value i.e. uphill. It terminates when it reaches a “peak”. Where no neighbor has a higher value. The algorithm does not maintain a search tree, so the current node data structure need only record the state and its objective function value. Hill – climbing does not look ahead beyond the immediate neighbors of the current state. This resembles trying to find the top of Mount Everest in a thick fog while suffering from amnesia.

function HILL – CLIMBING (problem) returns a state

inputs : problem, a problem

local variables : current, a node

neighbor, a node

current $\leftarrow$ MAKE – NODE (INITIAL – STATE [problem])

loop do

neighbor $\leftarrow$ a highest – valued successor of current

if VALUE [neighbor] $\leq$ VALUE [current] then return

STATE [current]

current $\leftarrow$ neighbor.

The Hill – Climbing search algo, which is the most basic local search technique. At each step the current node is replaced by the best neighbor, in this version, that means the neighbor with the highest VALUE, but if a heuristic cost estimate h is used, we would find the neighbor with the lowest h.

To illustrate hill – climbing, we will use the 8 – queens problem. Local search also typically use Complete state formulation. Where each state has 8 – queens on the board, one per column.

The successor function returns all possible states generated by moving a single queen to another square in the same column. (So each state has 8 x 7 = 56 successors)

The heuristic cost function h is the number of pairs of queens that are attacking each other, either directly or indirectly. The global minimum of this function is zero, which occurs only at perfect solutions.

Figure 4.12 (a) shows a state with h = 17.

The figure show the values of all its successors, with the best successors having h = 12. This algo choose randomly among the set of the best successors, if there is more than one. Hill climbing is sometimes called greedy local search because it grabs a good neighbor state without thinking ahead about where to go next.

Hill climbing often makes very rapid progress towards a solution, because it is usually quite easy to improve a bad state.

Example: From the state in figure 4.12 (a) if Local maximum – A state better than all of its neighbors, but not better than some other states far away. Takes just five steps to reach the state in figure 4.12 (b), which has h = 1R is very nearly a solution.

( $C_1, \ C_2, \ C_3, \ C_4, \ C_5, \ C_6, \ C_7, C_8 \ )$ = ( 5 6 7 4 5 6 7 6 )

Current state = h = 17. Hill climbing often get stuck for the following reasons:

- Local maxima: A local maximum is a peak that is higher than each of its neighboring states, but lower than the global maximum. Hill climbing algo that reach the vicinity of a local maximum will be drawn upwards towards the peak, but will then be stuck with nowhere else to go. Figure 4.10 illustrates the problem schematic more concretely, the state in figure 4.12 (b) is in fact a local maximum (i.e. a local minimum for the cost h), every move of a single queen makes the situation worse.

- Ridges: A ridge is shown in figure. Ridges result in a sequence of local maxima i.e. very difficult for greedy algorithm to navigate.

Figure 4.13 Illustration of why ridges cause difficulties for hill climbing. The grid of state (dark circles) is super imposed on a ridge rising from left to right, creating sequence of local maxima that are not directly connected to each other. For each local maximum, all the available actions. Point downhill.

- Plateau: A flat area of the search space in which all the neighboring states has the same rules.

- Plateaux: A Plate aux is an area of the state space landscape where, the evaluation function is flat. It can be a flat local maximum from which no up hill exit exists or a shoulder from which it is possible to make progress (see figure 4.10). A hill climbing search might be unable to find its way off the Plateau.