Breadth First Search (BFS):
BFS expands the leaf node with the lowest path cost so far, and keeps going until a goal node is generated. If the path cost simply equals the number of links, we can implement this as a simple queue (“first in, first out”).
his is guaranteed to find an optimal path to a goal state. It is memory intensive if the state space is large. If the typical branching factor is b, and the depth of the shallowest goal state is d – the space complexity is O(b^d), and the time complexity is O(b^d).
BFS is an easy search technique to understand. The algorithm is presented below.
breadth_first_search ()
{
store initial state in queue Q
set state in the front of the Q as current state ;
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 ;
else if (all states generated from current states are exhausted)
{
delete the current state from the Q ;
set front element of Q as the current state ;
}
else continue ;
}
} The algorithm is illustrated using the bridge components configuration problem. The initial state is PDFG, which is not a goal state; and hence set it as the current state. Generate another state DPFG (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 FDPG (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 GDFP.
Only three states can be generated from the initial state. Now the queue Q will have three elements in it, viz., DPFG, FDPG and GDFP. Now take DPFG (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 DGPF is reached.
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.
