Breadth First Search

BFS

Breadth First Search

Algorithm:

1) Store initial state in queue Q set state in the front of the Q as current state.

2) While (goal state is reached OR Q is empty)

{apply rule to generate a new state from the current state ; if

(new state is goal state) quit ;

3) Else if (all states generated from current states are exhausted) {delete the current state from the Q.

4) Set front element of Q as the current state.

Else continue.

The algorithm is illustrated using problem. The initial state is CADB, which is not a goal state; and hence set it as the current state.

Generate another state ACDB (by swapping 1st and 2nd position values) and add it to the list. That is not a goal state, hence; generate next successor state, which is DACB (by swapping 1st and 3rd position values). This is also not a goal state; hence add it to the list and generate the next successor state BADC.

Only three states can be generated from the initial state. Now the queue Q will have three elements in it, viz., ACDB, DACB and BADC. Now take ACDB (first state in the list) as the current state and continue the process, until all the states generated from this are evaluated.

Continue this process, until the goal state ABCD is reached. The order in which the states are generated and evaluated is shown in Figure.

The 14th evaluation gives the goal state. It may be noted that, all the states at one level in the tree are evaluated before the states in the next level are taken up; i.e., the evaluations are carried out breadth-wise. Hence, the search strategy is called breadth-first search.

BFS