Home | | Artificial Intelligence | | Computational Intelligence | | Artificial Intelligence | Best First Search: Concept, Algorithm, Implementation, Advantages, Disadvantages

Chapter: Artificial Intelligence

| Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail |

Best First Search: Concept, Algorithm, Implementation, Advantages, Disadvantages

Best first search is an instance of graph search algorithm in which a node is selected for expansion based o evaluation function f (n).

Best First Search

 

Best first search is an instance of graph search algorithm in which a node is selected for expansion based o evaluation function f (n). Traditionally, the node which is the lowest evaluation is selected for the explanation because the evaluation measures distance to the goal. Best first search can be implemented within general search frame work via a priority queue, a data structure that will maintain the fringe in ascending order of f values. This search algorithm serves as combination of depth first and breadth first search algorithm. Best first search algorithm is often referred greedy algorithm this is because they quickly attack the most desirable path as soon as its heuristic weight becomes the most desirable.

 

Concept:

 

Step 1: Traverse the root node

 

Step 2: Traverse any neighbour of the root node, that is maintaining a least distance from the root node and insert them in ascending order into the queue.

 

Step 3: Traverse any neighbour of neighbour of the root node, that is maintaining a least distance from the root node and insert them in ascending order into the queue

 

Step 4: This process will continue until we are getting the goal node

 

Algorithm:

 

Step 1: Place the starting node or root node into the queue.

 

Step 2: If the queue is empty, then stop and return failure.

 

Step 3: If the first element of the queue is our goal node, then stop and return success.

 

Step 4: Else, remove the first element from the queue. Expand it and compute the estimated goal distance for each child. Place the children in the queue in ascending order to the goal distance.

 

Step 5: Go to step-3

Step 6: Exit.

Implementation:


Let us solve an example for implementing above BFS algorithm.

 

Figure

 

Step 1:

 

Consider the node A as our root node. So the first element of the queue is A whish is not our goal node, so remove it from the queue and find its neighbour that are to inserted in ascending order.


 

Advantage:

 

It is more efficient than that of BFS and DFS.

 

Time complexity of Best first search is much less than Breadth first search.

 

The Best first search allows us to switch between paths by gaining the benefits of both breadth first and depth first search. Because, depth first is good because a solution can be found without computing all nodes and Breadth first search is good because it does not get trapped in dead ends.

 

Disadvantages:

 

Sometimes, it covers more distance than our consideration.

 

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail


Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.