Search code examples
algorithmtreetraversaltree-traversaltree-search

Steepest Ascent Hill Climbing vs Best First Search

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?

Solution

  • 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?