Trending Technology Machine Learning, Artificial Intelligent, Block Chain, IoT, DevOps, Data Science

Recent Post

Search

Saturday, 30 June 2018

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



No comments:

Post a Comment