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.

Answer 3

The difference lies in understanding what is more concerned in searching for the goal state.

Ask the question what is our aim... the final goal state? or the Best path to reach the goal state

The Best First Search is a systematic search algorithm where systematicity is achieved by moving forward iteratively on the basis of finding out the best heuristic value for the adjacent nodes for every current node.

Here the evaluation function ( heuristic function ) calculates the best possible path to achieve the goal state. So here we could see the Best First search is concerned about the best PATH to reach to the goal state.

However there are many problems where "Path to the Goal" is not a concern, the only thing is concerned is to achieve the final state in any possible ways or paths. (For eg: 8-queens problem).

Hence for this local search algorithms are used.

Local search algorithms operate using a single current node and generally move only to neighbor of that node.

Hill Climbing algorithm is a local search algorithm. So here we need to understand the approach to get to the goal state not the best path to reach when thinking about hill climbing.

(As stated in AI-A Modern Approach,SR & PN)

Basically, to understand local search we need to consider state-space landscape.

A landscape has both

(i) location (defined by the state) and

(ii) Elevation (defined by the value of heuristic function or objective function)

We need to understand the two types of elevations,

(i) If elevation corresponds to an objective function,then the aim is to find the highest peak i.e. a Global Maximum.

(So these type of elevation are useful in different scenarios which are not concerned with cost and which are only concerned with finding the best instant moves)

(ii) If elevation corresponds to cost, then the aim is to find the lowest valley i.e. a Global Minimum.

(Here is the common thing i.e. Steepest(always stepping up with better estimations i.e. no plateau problem or any other) hill climbing is similar to Best First Search. Here the elevation function is the heuristic function which provide the best minimum cost. And hill climbing here is only concerned with current node and iterates through the adjacent nodes for minimum value and proceeds with expanding the best node which is similar to Best First Search)

Note:

Hill Climbing algorithm does not look ahead beyond the immediate neighbors of the current state. It is only concerned with best neighboring node to expand.And the best neighboring is decided by the above evaluations functions.

Whereas, Best First Search algorithm look ahead of the immediate neighbors to find the best path to the goal(using Heuristic evaluation) and then proceeding with the best one. So difference lies in approach of local searches and systematic search algorithms.

Understand the difference in approaches, you will get to know why both are named different.

Answer 4

Let me Wiki that for you:

In simple hill climbing, the first closer node is chosen, whereas in steepest ascent hill climbing all successors are compared and the closest to the solution is chosen.

...

Steepest ascent hill climbing is similar to best-first search, which tries all possible extensions of the current path instead of only one.

Answer 5

So Basically Steepest HC in the second step itself gets the answer to the problem as it's second move will be the most optimal solution and leading to the answer