Breadth-first Search (BFS) in AI

Breadth first search (BFS), as the name implies, search from the initial state breadth-wise.

That is it searches all the states in the tree level by level.

Only after exploring all the states in one level it will jump to the next level.

Once the solution is found the search stops.

The breadth first search is guaranteed to find the solution if one exists.

Expand shallowest unexpanded node

Implementation:

A breadth-first search (BFS) explores nodes nearest the root before exploring nodes further away.

For example, after searching A, then B, then C, the search proceeds with D,E,F,G

Node are explored in the order A B C D E F G H I J K L M N O P Q

J will be found before N

 

Algorithm :-

function breath_first_search;

                Nodes are lining up to be visited in open

                closed keeps track of all the nodes visited already.

begin   

  open := [Start];                                              % initialize

  closed := [];

  while open ≠ [] do                                       % states remain

      begin

remove leftmost state from open, call it X;

    if X is a goal then returns SUCCESS                 % goal found

        else begin

               generate children of X;

               put X on closed;

               discard children of X if already on open or closed;            % loop check

               put remaining children on right end of open                         % queue

             end

     end

  return FAIL                                                                             % no states left

end.

A trace of breadth-first algorithm

1. open = [A]; closed = []

2. open = [B,C,D]; closed = [A]

3. open = [C,D,E,F]; closed = [B,A]

4. open = [D,E,F,G,H]; closed = [C,B,A]

5. open = [E,F,G,H,I,J]; closed = [D,C,B,A]

6. open = [F,G,H,I,J,K,L]; closed = [E,D,C,B,A]

7. open = [G,H,I,J,K,L,M] (as I. is already on open); closed = [F,E,D,C,B,A] 

8. open = [H,I,J,K,L,M,N] closed = [G,F,E,D,C,B,A] 

9. and so on until either goal is reached or open is empty.
 

Properties of Breadth-first search

Complete? Yes  (if b is finite)

Time? (O (b d+1)

Space? (keeps every node in memory)

Optimal? Yes (if cost = 1 per step)

Space is the bigger problem (more than  time) 

Breadth-first search tree sample

Branching factor :- number of nodes generated by a node parent (we called here "b")e

⇒ Here after b=2 

 Breadth First Complexity

The root⇒generates (b) new nodes

Each of which ⇒ generates (b) more nodes

So, the maximum number of nodes expended before finding a solution at level "d"

Complexity is exponential = O(bd)

Time and memory requirement in Breadth-first