SEE THE SOURCES USED FOR THE GLOSSARY DEFINITIONS HERE

HILL CLIMBING

Sometimes called greedy local search, it is an algorithm that continually moves in the direction of increasing the value of the objective function (that is, uphill). It terminates when it reaches a peak where no neighbor has a higher value. It often fails to find a goal when one exists because it can get stuck on local maxima so it is incomplete.

HILL CLIMBING ALGORITHM

node ← create node with STATE = problem.INITIAL-STATE, VALUE = problem.OBJECTIVE-FUNCTION(STATE) WHILE (true) best-neighbor ← null FOR EACH operator IN problem.LEGAL-OPERATORS(node.STATE) neighbor ← create node with STATE = problem.APPLY(operator, node.STATE), VALUE = problem.OBJECTIVE-FUNCTION(STATE) IF best-neighbor is null THEN best-neighbor ← neighbor ELSE IF neighbor.VALUE > best-neighbor.VALUE THEN best-neighbor ← neighbor END IF best-neighbor.VALUE < node.VALUE THEN return node node ← best-neighbor END