# New Technology

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

## Saturday, 30 June 2018

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.

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.

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)

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

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