Artificial Intelligence – Breadth First Search(BFS)

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

Now let us apply the algorithm on the above tree and see what it gives us. We will assume that the edge S->G is not present in the graph. 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 ] }
Iteration2: { [ S->A->B ], [ S->A->C ] }
Iteration3: { [ S->A->B->D ], [ S->A->C->D ], [ S->A->C->G ] }
Iteration4 gives the final output as S->A->C->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.

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!

Advertisements

8 comments

  1. praveen · · Reply

    cant you explain the other possibility??the one example which you ve explained above was worth nothing.because another part of the tree is deep.so you couldve demonstrated the example in a
    more convinent way.

  2. Hi Praveen,
    Thanks for the suggestion. I have made a change in the example accordingly. Please try and be a little polite next time.

  3. Nice tutorial, another video explanation

  4. Hello,

    Thanks for the great explanation.
    I have a question about about how did you get the result “S->A->C->G” for when there is a cost for the paths? Why it didn’t go S->A->C->D->G?

    1. Thanks for appreciating. I don’t quite understand your question. As I have mentioned above, the algorithm does not work for graphs which have weights assigned to edges. It assumes a weight of 1 for every edge. And in that case, S->A->C->G is clearly shorter than S->A->C->D->G.

  5. Why do you say the final output is S-A-C-G? is the optimal path not S-G?

    1. Hi Dennis,

      I think you missed the statement written in bold after I mentioned the algorithm. ‘We will assume that the edge S->G is not present in the graph’.

  6. Thanks alot! Great post!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: