Coolest hilltop climb and best first search
I am trying to solve the problem using different algorithms and the Steepest Ascent Climbs (SAHC) and Best First Search are two of those algorithms that I need to implement.
According to Wikipedia:
"In the steepest ascent, the hill climbs all the successors, and the closest to the solution is chosen ..."
"The steepest climbing climb is like the best search that tries every possible extension of the current path, not just one."
SAHC : all followers are compared and the closest to a solution are selected.
BestFS : Handles all possible extensions of the current path, not just one.
I really don't understand how they differ. Can anyone help me on this, preferably with some kind of explanation using trees?
source to share
They are very similar. The difference is that a first-order search looks at all paths from the beginning of a node to the end of a node, whereas the steepest climb in an ascent only remembers one path during the search.
For example, let's say we have a graph like
start ---- A ---- B ---- end
\ /
------\ /---------
\ /
C
where each edge has the same weight: ignore my shitty ASCII art skills :). Also assume that in our heuristic function, A is counted closer to the end than C. (This could still be a valid heuristic - it just underestimates the true distance of A.)
Then climbing a steep slope will first select A (because it has the lowest heuristic value), then B (since its heuristic value is below the starting node), and then the end node.
On the other hand, the best search is
- Add A and C to the open list.
- Take A, the best value, from the open list and add B. Then OPEN = {B, C}.
- Take the best node from the open list (either B or C, and more than a second later), and add its successor, target state.
- Take the state of the target off the open list and return the path that was there.
The choice of B or C in step 3 depends on the exact algorithm used to find the best first. A * would evaluate a node as a cost to get there plus a cost to get to the end, in which case C (and in fact, with a valid heuristic, A * is guaranteed to always be the optimal path for you). Greedy Best Search will choose between the two options arbitrarily. In any case, the search contains a list of possible locations, not just one.
More clearly, how do they differ from each other now?
source to share
SAHC is going to eagerly choose one (possibly suboptimal) path - it will simply use the best node at each step until it reaches the goal.
Your best bet, on the other hand, is to generate the entire search tree. Often (in the case of A *) it will find the optimal solution, this is not guaranteed for SAHC.
source to share
Don't know how to add a flag to insert it again, Sorry about that. So here is what I got as a difference.
The difference lies in understanding what is more of a concern when looking for a target state .
Ask a question what is our goal ... the state of the ultimate goal ? or The best way to achieve goal state
Best First Search is a systematic search algorithm in which systematicity is achieved by moving forward iteratively based on determining the best heuristic value for adjacent nodes for each current node.
Here, the scoring function (heuristic function) calculates the best possible path to achieve the target's goal . So we saw that the Best First search bothers about the best PATH to achieve the goal.
However, there are many problems when the " Way to the goal " is not a problem , the only thing that concerns to reach the final state by any means or means. (For example: the 8 kings problem ).
Therefore, local search algorithms are used for this .
Local search algorithms work using a single current node, and usually only for the neighboring node.
Hill Climbing is a local search algorithm . Therefore, here we need to understand the approach to get to the goal state, not the best way to achieve when you think about climbing a hill.
(As stated in AI-A Modern Approach, SR and PN )
Basically, to understand local search, we need to consider the state landscape .
A landscape has both
(i) location (determined by the state) and
(ii) Height (determined by the value of the heuristic function or objective function )
We need to understand two types of elevations ,
(i) If the height matches the objective function, then the goal is to find the highest peak, i.e. global maximum .
(So this type of boost is useful in a variety of scenarios that are not costly and that only involve finding the best instant moves)
(ii) If the altitude matches the value , then the goal is to find the lowest valley, i.e. Global minimum .
( Here's a common thing , ie steep (always rising with better grades, ie plateau problem or whatever), climbing a hill is like “Best First Search.” Here the function is a heuristic function that provides the best minimum value . And the hill climb here only deals with the current node and iterations through adjacent nodes for the minimum and continues with expanding the best node, which is similar to Best First Search )
Note :
Hill Climbing does not look ahead outside the immediate neighbors of the current state . It only deals with the best siblings to expand. And the best neighborhood is determined by the above evaluation functions.
Whereas the Best First Search algorithm looks ahead of the nearest neighbors to find the best path to the target (using a heuristic estimate) and then go for the best. Thus, the difference lies in the approach of local searches and systematic search algorithms.
Understand the difference in approach, you will find out why both are named different.
source to share