Best-first search algorithm always selects the path which appears best at that moment. It is also called as Greedy search. It is the combination of Breadth First Search (BFS) and Depth First Search (DFS) algorithms. it uses the heuristic function and search. best-first search allows us to take the advantages of both the algorithms. At each step we can choose most promising node with the help of best-first search. we expand the node which is closest to the goal node and the minimum cost is estimated by the heuristic function. It is implemented by the priority queue.

Algorithm:

• 1. Place the starting node into the OPEN list.
• 2. If the OPEN list is empty, stop and return failure.
• 3. Remove the node n, from the OPEN list which have the lowest value of h(n), and place it in the closed list.
• 4. Expand the node n, and generate the successors of node n.
• 5. Check each successor of node n, and find whether anu node is goal-node or not, if it finds return success and terminate the search, else proceed to next step (step-6).
• 6. For each successor node, algorithm checks for evaluation function f(n), and check if the node has been either open or closed list. If the node has not been in both the list then add it to the OPEN list.
• 7. Return to step 2.

Advantages

• • Best first search use both BFS and DFS algorithms so it is gaining advantages of both the algorithms.
• • It is more efficient than BFS and DFS.

Disadvantages:

• • It can get stuck in a loop like as DFS
• • It is not optimal
• • It can behave like an unguided depth-first search in the worst case.

Time Complexity:

The worst-case time complexity is O(b^m)

Space Complexity:

The worst-case space complexity is O(b m ), where m is the maximum depth of the search space.

Complete:

Greedy best-first search algorithm is incomplete, even if the given state space is finite.

Optimal:

greedy best-first search algorithm is not optimal.

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc