4

I am trying to solve a problem using different algorithms and Steepest Ascent Hill Climbing (SAHC) and Best First Search are two of these algorithms that I need to implement.

According to Wikipedia:

"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."

SAHC: All successors are compared and the closest to the solution is chosen.
BestFS: Tries all possible extensions of the current path instead of only one.

I don't really understand how these are different. Could some please help me with this, preferably with some sort of an explanation using trees?

goodmanship
  • 334
  • 1
  • 13
karancan
  • 2,152
  • 4
  • 23
  • 35

3 Answers3

13

They are quite similar. The difference is that best-first search considers all paths from the start node to the end node, whereas steepest ascent hill climbing only remembers one path during the search.

For example, say we have a graph like

start ---- A ---- B ---- end
  \                     /
   ------\    /---------
          \  /
           C

where each edge has the same weight: ignore my crappy ASCII art skills :). Also suppose that in our heuristic function, A is considered as closer to the end than C. (This could still be an admissible heuristic – it just underestimates the true distance of A.)

Then steepest-ascent hill climbing would choose A first (because it has the lowest heuristic value), then B (because its heuristic value is lower than the start node's), and then the end node.

A best-first search, on the other hand, would

  1. Add A and C to the open list.
  2. Take A, the best value, off the open list, and add B. Then OPEN = {B, C}.
  3. Take the best node off the open list (either B or C, more on that in a second), and add its successor, the goal state.
  4. Take the goal state off the open list and return the path that got there.

The choice of B or C in step 3 depends on exactly the best-first search algorithm you're using. A* would evaluate the node as the cost to get there plus the estimate of the cost to get to the end, in which case C would win (and in fact, with an admissible heuristic, A* is guaranteed to always get you the optimal path). A "greedy best-first search" would choose between the two options arbitrarily. In any case, the search maintains a list of possible places to go from rather than a single one.

Is it clearer how the two are different now?

Danica
  • 28,423
  • 6
  • 90
  • 122
  • Very comprehensive! Thank you – karancan Feb 07 '13 at 02:41
  • So basically, steepest hill climbing will look for the next best vertex from the current vertex, and not from the source (first) vertex? – goelakash Sep 20 '15 at 19:37
  • 2
    @goelakash Yes, steepest hill climbing keeps a current position and looks for the next best vertex to take. – Danica Sep 20 '15 at 22:10
  • Does Steepest Hill Climbing maintain a Closed list too? – CodyBugstein Oct 04 '15 at 17:23
  • @CodyBugstein Steepest Ascent Hill Climbing does not need to keep a closed list because it will always go down the path as long as the next value is better than the current one, it will never reach the same node twice. – Mirodinho Oct 16 '17 at 13:51
4

SAHC is going to choose a single, (possibly non-optimal) path greedily - it'll simply take the best node at each step until it hits the target.

Best-first, on the other hand, generates an entire search tree. Often (in the case of A*) it will find the optimal solution, this is not guaranteed for SAHC.

dfb
  • 13,133
  • 2
  • 31
  • 52
0

Dint know how to flag so pasted it again, Sorry for that. So here goes what I got as a difference.

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.

Reck
  • 1,388
  • 11
  • 20