Hill Climbing Algorithm in Artificial Intelligence

Hill Climbing:

Hill Climbing is an optimization technique that belongs to the family of local search. It is a relatively simple technique to implement, making it the first choice. Although more advanced algorithms may give better results, there are situations where hill climbing works well.

It is called hill climbing because of the way the nodes are selected for expansion. At each point in the search, a successor node that appears to lead most quickly to the top of the hill(goal) is selected for exploration.

In this method of searching, the generate and test algorithm is augmented by a heuristic foundation that measures the closeness of the current state to the goal state. Hill climbing can be implemented if the path to the goal doesn’t matter. It is a local search method in which we consider the state space landscape.

Hill Climbing Algorithm:

Step1: Put the initial node on a list, START-LIST.

Step2: If (START-LIST is empty) or (START-LIST is GOAL) then terminate search.

Step3: Removes the first node from the START-LIST, call this node, n.

Step4: If(n=GOAl) then terminate search with SUCCESS.

Step5: Else if a node, n has successors then generate all of them. Find how far they are from the goal node. Sort them by the remaining distance from the goal and add them to the beginning of START-LIST.

Step 6: Goto Step 2.