In this post I will talk about the Breadth First Search algorithm for solving a search problem. Given below are the diagrams of the example search problem and the created search tree. If you don’t know what search problems are and how search trees are created visit this post.
Breadth First Search
Breadth First Search is a great algorithm for getting the shortest path to your goal(not applicable to graphs which have weights assigned to edges). Breadth First Search by the name itself suggests that the breadth of the search tree is expanded fully before going to the next step.
Now unlike Depth First Search we don’t need a priority queue for this. We use two queues instead, one for expanding and one for temporary storing. Again each element of the queue is a path from the root of the tree. The algorithm using these queues is the following:
Insert the root into the expanding queue
While expanding queue is not empty
Copy contents of expanding queue to temporary queue
Empty the expanding queue
For each node in the temporary queue
Dequeue one element from the temporary queue
If the path is ending in the goal state, print the path and exit
Else
Insert all the children of the dequeued element into the expanding queue
While expanding queue is not empty
Copy contents of expanding queue to temporary queue
Empty the expanding queue
For each node in the temporary queue
Dequeue one element from the temporary queue
If the path is ending in the goal state, print the path and exit
Else
Insert all the children of the dequeued element into the expanding queue
Now let us apply the algorithm on the above tree and see what it gives us. We will write down the state of the expanding queue at each iteration and look at the final output. Each element of the queue is written as [path].
Initialization: { [ S ] }
Iteration1: { [ S->A ] , [ S->G ] }
Iteration2 gives the final output as S->G.
Iteration1: { [ S->A ] , [ S->G ] }
Iteration2 gives the final output as S->G.
Things worth mentioning:
->The creation of the search tree is not a part of the algorithm. It is only for visualization.
->The algorithm returns the first possible path encountered(in this case optimal), it does not search for all possible paths.
->The returned path is the shortest possible path in the search tree.
->The algorithm returns the first possible path encountered(in this case optimal), it does not search for all possible paths.
->The returned path is the shortest possible path in the search tree.
It searches the tree level by level, i.e. expands all possible paths till each node at a particular height and then goes for the level below. Thus it is rightly called Breadth First Search. This also explains why we did not require the priority queue used in Depth First Search. Remember that the priority of each element was the number of nodes that the path contained. Here, each element has the same number of nodes since we are expanding level by level, and thus having a priority does not make sense.
I mentioned before that Breadth First Search is not optimal for graphs having weights assigned to edges. An example of such a graph is given below:
For this example Breadth First Search will return the path as S->G whereas the path having minimum cost associated with it is S->A->C->G. Thus Breadth First Search returns the path shortest in length and not optimal in cost. We shall solve this problem by using Uniform Cost Search in the next post!
