Catalogue of Artificial Intelligence Techniques
Author(s): Rina Dechter
Hill climbing is a search method for finding a maximum (or minimum) of an evaluation function. It considers the local neighbourhood of a node, evaluating each neighbour node, and next examines those nodes with the largest (or smallest) values. Unlike other search strategies that use evaluation functions (e.g., the A* algorithm or informed Depth-first Search) hill climbing is an irrevocable scheme: it does not permit us to shift attention back to previously suspended alternatives, even though they may have offered a better alternative than the ones at hand. This property is at the heart of both its computational simplicity and its shortcomings; it requires very little memory since alternatives do not need to be retained for future consideration. However, it is not guaranteed to lead to a solution, since it can get stuck on a plateau or a local optimum, or even wander on infinite uncontrolled paths, unless the guiding evaluation function is very informative.
- Pearl, J., Heuristics: intelligent search strategies for
computer problem solving
, Addison-Wesley, Reading, Mass. and London , 1984, pp.35--36.