Hill Climbing Algorithm

Suppose the graph (figure 6(a)) is drawn showing interconnected cities. It is a two way graph. A person can move in any direction like from node 2 to node 4 or from node 4 to node 2. An edge tells the distance between two connected cities. Different search algorithms use different strategies to find path from source node to destination node. Here is explanation of how Hill Climbing works.

Figure 6(a)

Hill Climbing
Hill climbing is a local search. It looks for local maxima to reach from source node to goal node. It looks for node closer to destination node and then extend path from current node. But limitation is that it looks for only local maxima. A local maximum is having the highest value among its neighbouring nodes but less than node in global space. So it get stucked if there is no another better node in local search space. It does not look for global search space.

Suppose for above drawn graph (figure 6(a)) showing connected cities
Source node – 3
Destination node – 5

1. Source Node is 3, which is shown in figure 6(b) with another circle of red colour.

Figure 6(b)

2. It will look for neighbouring nodes of Node 3. Node 2 and Node 4 are its neighbouring nodes. So it path will extend towards Node 4 which seems to be more closer to solution node as shown in figure 6(c)

Figure 6(c)

3. Node 2 is found to be near to destination node, so is explored next as shown in fig 6(d).

Figure 6(d)

But now there is no other node near to this local search. Hill Climbing cannot look for global search so it cannot move to next node. Hence it is stucked here. This is incomplete search.