What is the difference between Hill Climbing Search and Best First Search?

Question

I am trying to learn some search concepts but ran into a wall in the process. Can anyone explain to me what the difference is between hill climbing search and best first search? To me, they both look like expanding the nodes with the heuristic value closest to the goal. If anyone can explain the difference to me, it'd be greatly appreciated. Thanks!

Answer 1

You can view search algorithm as having a queue of remaining nodes to search. This answer demonstrates this principle.

In depth-first search, you add the current node's children to the front of the queue (a stack). In breadth-first search, you add the current node's children to the back of the queue. Think for a moment about how this leads to the right behaviour for those algorithms.

Now, in hill-climbing search, you sort[1] the current node's children before adding them to the queue. In best-first search, you add the current node's children to the queue in any old order, then sort[1] the entire queue. If you think about the effect that might have on the order in which nodes are searched, you should get an idea of the practical difference.

I found this concept too tangly to understand from purely abstract terms, but if you work through a couple of examples with a pencil it becomes simple.

[1]: sort according to some problem-specific evaluation of the solution node, for example "distance from destination" in a path-finding search.

Answer 2

A liitle late, but here goes.

In BFS, it's about finding the goal. So it's about picking the best node (the one which we hope will take us to the goal) among the possible ones. We keep trying to go towards the goal.

But in hill climbing, it's about maximizing the target function. We pick the node which provides the highest ascent. So unlike BFS, the 'value' of the parent node is also taken into account. If we can't go higher, we just give up. In that case we may not even reach the goal. We might be at a local maxima.