mockup, typewriter, word

Informed (Heuristic) Search Strategies: Greedy best-first search

What is Informed Search:

Informed Search refers to search algorithms which help in navigating large databases with certain available information about the end goal in search and most widely used in large databases where uninformed search algorithms can’t accurately curate precise results.

Heuristic Function:

•A Heuristic (or a heuristic function) takes a look at search algorithms. At each branching step, it evaluates the available information and makes a decision on which branch to follow.

• A key component of an evaluation function is a heuristic function
h(n), which estimates the cost of the cheapest path from node n
to a goal node

Let us now head towards the topic, Greedy Breadth First Search.

• Greedy best-first search 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, the evaluation function is f(n) = h(n)
• E.g. in minimizing road distances a heuristic lower bound for distances of cities is their straight-      line distance.
• Greedy search ignores the cost of the path that has already been traversed to reach n.                     Therefore, the solution given is not necessarily optimal.
• If repeating states are not detected, greedy best-first search may oscillate forever between two     promising states.
• Because greedy best-first search can start down an infinite path and never return to try other         possibilities, it is incomplete
• Because of its greediness the search makes choices that can lead to a dead end; then one               backs up in the search tree to the
deepest unexpanded node
• Greedy best-first search resembles depth-first search in the way it prefers to follow a single            path all the way to the goal, but will back up when it hits a dead end.
• The worst-case time and space complexity is O(bm).
• The quality of the heuristic function determines the practical usability of greedy search.

Let us understand the greedy breadth first search with the help of an example.

As you can see in the Above Tree diagram, the following is the tree with each node having F(n) Values.

Here the problem is how can we find a path from start node(S) to the goal node(E) with the most optimal path .

Step 1: traverse the starting node S, which has node A,B & C.
Step 2:Now Visit the node having the lowest F(n) value which will be c, Now same step has to be repeated.

Step 3:As Node I & M do not lead us to the goal, We have to go back to S and find the smallest node (we can not traverse node C as it is previously visited) .So we visit the node B and then same repeat the step 2 of finding the node with smallest F(n) value.

Step 4:After Following the step 3 we reach the Goal node (E) with the most optimal path.

Now ,What are the disdvantages of the GBFS:

• Not complete
– Gets stuck on local minimas and plateaus
• Infinite loops
• Irrevocable
• Not optimal

As we learned more about GBFS we come to know that once a node is skipped it cannot be traversed again. The algo is better than the uninformed search but it has many flaws like getting stuck in infinite loops . So there are many other search algorithms which are more efficient and faster than it like A* Algorithm .

Thank You Guys For Visiting Here!

Make Sure To Comment And Share Whether You Grasp The Above Topic.

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Shopping Cart