Breadth First Search (BFS)| 4th and 5th Semester | Cognitive Science and AI | BSc.CSIT (TU)

Breadth First Search (BFS) | Fourth and Fifth Semester Second Year | Tribhuvan University (TU) Subject: Cognitive Science and AI | BSc.CSIT

All nodes are expended at a given depth in the search tree before any nodes at the next level are expanded until the goal reached.
Expand shallowest unexpanded node.
Constraint: Do not generate as child node if the node is already parent to avoid more loop.

BFS Evaluation:

Completeness:

• Does it always find a solution if one exists? ;- YES –> If shallowest goal node is at some finite depth d and If b is finite

Time complexity:

• Assume a state space where every state has b successors.
• root has b successors, each node at the next level has again b successors (total b2), …
• Assume solution is at depth d
• Worst case; expand all except the last node at depth d
• Total no. of nodes generated:
b + b2 + b3 + ………………….. bd + ( bd+1 –b) = O(bd+1)

Space complexity:

• Each node that is generated must remain in memory
• Total no. of nodes in memory:
1+ b + b2 + b3 + ………………….. bd + ( bd+1 –b) = O(bd+1)