Breadth First Search
Breadth first search is a search strategy which performs step by step i.e., expands the root node, expand all successors of root node, then successor of resulting nodes and so on. This process goes on till the goal state or solution is obtained.
Breadth first search is a search strategy which expands all the nodes at a particular level of a search tree with respect to the given depth and then proceeds to the next level of nodes.
Consider the problem tree given in Figure
The above Figure shows how breadth first search algorithm search the tree (of above figure) to reach the goal node (i.e,, 7).
We can implement breadth first search by using GENERAL -TREE SEARCH algorithm with First In First Out (FIFO) queue.
Breadth first search Is complete i.e., if the goal node is present at a depth 'd' then breadth first search will find it only after expanding all the nodes till that depth 'd'.
Algorithm
- A variable NL is create Which must be set to the initial state.
- Repeat the steps mentioned below till the goal state is obtained or NL is empty.
- From NL remove the first element and name it as ‘M’. If NL is empty then quit.
- Do the following for each rule that matches the state described in 'M'.
- Generate a new state by applying the rule.
- Check whether the new state is goal state, if yes then quit and return the state.
- Otherwise, append the new state of NL.
Advantages
- It definitely finds a solution provided that a solution is available.
- Finds the minimal solution from the multiple solutions.
- Explores all the shorter paths first before exploring the larger paths.
Disadvantages
- It consumes large amount of space as well as time.
- It is considered only when the branching factor is small
