**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