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