# 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)

• if all paths have the same cost. Otherwise, not optimal but finds solution with shortest path length (shallowest solution). If each path does not have same path cost shallowest solution may not be optimal
(Visited 263 times, 1 visits today)

Posted By : | Comment RSS | Category : Fifth Semester, Fourth Semester
Subscribe Notes