This is a variation of Simple Hill Climbing which considers all the moves from the current state and selects the best one as the next state.
At each current state we select a transition, evaluate the resulting state, and if the resulting state is an improvement we move there, otherwise we try a new transition from where we were.
We repeat this until we reach a goal state, or have no more transitions to try.
The transitions explored can be selected at random, or according to some problem specific heuristics.
Algorithm:
Hill climbing has three well-known drawbacks:
- Local Maxima: A local maximum is a state that is better than all its neighbours but is not better than some other states further away.
- Plateau: A plateau is a flat area of the search space in which, a whole set of neighbouring states have the same values.
- Ridge: Ridge is a special kind of local maximum. It is an area of the search space that is higher than surrounding areas and that itself has slop.
In each of the previous cases (local maxima, plateau & ridge), the algorithm reaches a point at which no progress is being made.
A solution is,
- Backtrack to some earlier node and try going in a different direction.
- Make a big jump to try to get in a new situation.
- Moving in several directions at once.
