Best First Search

Best-First Search Algorithm
Best-first search is a systematic control strategy, combining the strengths of breadth-first and depth-first search into one algorithm. The main difference between best-first search and the brute-force search techniques is that we make use of an evaluation or heuristic function to order the SearchNode objects on the queue. In this way, we choose the SearchNode that appears to be best, before any others, regardless of their position in the tree or graph.
It tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly. Thus, it evaluates nodes by using just the heuristic function: f (n) = h(n).
Main Program of Best-Search Algorithm

Characteristics of Best First Search


• Like the depth-first and breadth-first search, best-first search uses two-lists. open: to keep track of the frontier of the search. closed: to record states already visited.
• Order the states on open according to some heuristic estimate of their closeness to a goal.
• At each iteration through the loop, consider the most promising state on the open list next.
• When visiting a child state, if it is already on open or closed, the algorithm checks if the child is reached by a shorter path this time compared with the last time it arrived at this child.

Greedy Search Algorithm
Greedy search is a best-first strategy where we try to minimize the estimated cost to reach the goal. Since we are greedy, we always expand the node that is estimated to be closest to the goal state. Unfortunately, the exact cost of reaching the goal state usually can’t be computed, but we can estimate it by using a cost estimate or heuristic function h(). When we are examining node n, then h(n) gives us the estimated cost of the cheapest path from n’s state to the goal state. Of course, the better an estimate h() gives, the better and faster we will find a solution to our problem. Greedy search has similar behavior to depth-first search. Its advantages are delivered via the use of a quality heuristic function to direct the search.