Catalogue of Artificial Intelligence Techniques


Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML

Hill Climbing

Categories: Search

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.



Add Comment

No comments.