We will be covering:
- Best-first Search
- Greedy Best First Search Algorithm
The best first search considers all the open nodes so far and selects the best amongst them. The following sequence of diagrams will show you how a best-first search procedure works in a search tree.
• We start with a search tree as shown above. From S we observe that A is the best option so we explore A.
• At A we now have C, E, D, and B as the options. We select the best of them which is D.
• At D we have S, G, B, H, M and J as the options. We select H which is the best of them.
• At last from H we find L as the best.
Hence best-first search is a greedy approach that will look for the best amongst the available options and hence can sometimes reduce the searching time. All these heuristically informed procedures are considered better but they do not guarantee the optimal solution, as they are dependent on the quality of heuristic being used.
Also Read: Shell Scripting – Variables
Algorithm of Best first Search:
This Best-First search algorithm has two versions; Greedy best-first search and A*. In both versions, the algorithm remains the same while heuristic is evaluated with different factors. Greedy search works only on h(n), heuristic discussed so far, while A* works on F(n)=g(n) + h(n).
Heuristics are fallible, it can mislead. If two states having the same heuristics value at some middle phase, it does not mean that both will provide you the shortest path. Whenever such a situation occurs it is better to examine the state that is nearest to the root state of the graph. Among the two sates having the same heuristic, the state whose distance is shorter from start state will have a greater probability of being on the shortest path to the goal.
The distance from the root can be measured by maintaining a depth count for each state. BY accommodating this information our heuristic function will become as
g(n) measure the distance from any state ‘n’ to start state.
h(n) is a heuristic estimate of the distance from state n to a goal.
After assigning heuristics value we can apply a best-first algorithm to search for a goal.