How Greedy Best-First Search Works?
- Greedy Best-First Search works by evaluating the cost of each possible path and then expanding the path with the lowest cost. This process is repeated until the goal is reached.
- The algorithm uses a heuristic function to determine which path is the most promising.
- The heuristic function takes into account the cost of the current path and the estimated cost of the remaining paths.
- If the cost of the current path is lower than the estimated cost of the remaining paths, then the current path is chosen. This process is repeated until the goal is reached.
An example of the best-first search algorithm is below graph, suppose we have to find the path from A to G
The values in red color represent the heuristic value of reaching the goal node G from current node
1) We are starting from A , so from A there are direct path to node B( with heuristics value of 32 ) , from A to C ( with heuristics value of 25 ) and from A to D( with heuristics value of 35 ) .
2) So as per best first search algorithm choose the path with lowest heuristics value , currently C has lowest value among above node . So we will go from A to C.
3) Now from C we have direct paths as C to F( with heuristics value of 17 ) and C to E( with heuristics value of 19) , so we will go from C to F.
4) Now from F we have direct path to go to the goal node G ( with heuristics value of 0 ) , so we will go from F to G.
5) So now the goal node G has been reached and the path we will follow is A->C->F->G .