Breadth-first search Example Advantages and Disadvantages

Explain Breadth-first search (BFS) with an example. List down the advantages and disadvantages of BFS – Artificial Intelligence

Breadth-first search (BFS)

Breadth-First –Search is an uninformed search technique. Consider the state space of a problem that takes the form of a tree. Now, if we search the goal along with each breadth of the tree, starting from the root and continuing up to the largest depth, we call it breadth-first search.

Algorithm: Breadth-First Search

1. Create a variable called NODE-LIST and set it to the initial state. 
2. Until a goal state is found or NODE-LIST is empty: 
   a)Remove the first element from NODE-LIST and call it E. 
     If NODE-LIST was empty. quit. 
   b)For each way that each rule can match the state described in E do: 
      i)   Apply the rule to generate a new state, 
      ii)  If the new state is a goal state. quit and return this state. 
      iii) Otherwise, add the new state to the end of NODE-LIST 

Breadth-First Search – Example

Let us consider the following tree. Here node ‘A’ is the source or start or initial node and node ‘G’ is the goal node.

BFS 1

Step 1: Initially NODE-LIST contains only one node corresponding to the source state A.

See also  Means-Ends Analysis Artificial Intelligence

NODE-LIST: A

Step 2: Node A is removed from NODE-LIST. The node is expanded, and its children B and C are generated. They are placed at the back of NODE-LIST.

NODE-LIST: B C

BFS 2

Step 3: Node B is removed from NODE-LIST and is expanded. Its children D, E are generated and put at the back of NODE-LIST.

NODE-LIST: C D E

BFS 3

Step 4: Node C is removed from NODE-LIST and is expanded. Its children D and G are added to the back of NODE-LIST.

NODE-LIST: D E D G

BFS 4

Step 5: Node D is removed from NODE-LIST. Its children C and F are generated and added to the back of NODE-LIST.

NODE-LIST: E D G C F

BFS 6

Step 6: Node E is removed from NODE-LIST. It has no children.

NODE-LIST: D G C F

BFS 7

Step 7: D is expanded; B and F are put in OPEN.

NODE-LIST: G C F B F

BFS 88

Step 8: G is selected for expansion. It is found to be a goal node. So the algorithm returns the path A C G by following the parent pointers of the node corresponding to G. The algorithm terminates.

BFS Goal State

Advantages of Breadth-first search are:

See also  Problem Characteristics in Artificial Intelligence

One of the simplest search strategies.

Complete. If there is a solution, BFS is guaranteed to find it.

If there are multiple solutions, then a minimal solution will be found

The algorithm is optimal (i.e., admissible) if all operators have the same cost. Otherwise, breadth-first search finds a solution with the shortest path length.

Finds the path of minimal length to the goal.

Disadvantages of Breadth-first search are:

Requires the generation and storage of a tree whose size is exponential to the depth of the shallowest goal node.

The breadth-first search algorithm cannot be effectively used unless the search space is quite small.

Summary

This article discusses breadth-first search (BFS) with an example. Also, advantages and disadvantages of BFS – Artificial Intelligence. If you like the material share it with your friends. Like the Facebook page for regular updates and YouTube channel for video tutorials.

Leave a Comment

Your email address will not be published.