[wptelegram-join-channel]

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

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.

```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
```

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.

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.