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.
Step 1: Initially NODE-LIST contains only one node corresponding to the source state A.
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
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
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
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
Step 6: Node E is removed from NODE-LIST. It has no children.
NODE-LIST: D G C F
Step 7: D is expanded; B and F are put in OPEN.
NODE-LIST: G C F B F
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.
Advantages of Breadth-first search are:
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.