Recently MeroSpark is lunched with more features and services, now you can ask your question, sell your books, share your notes and many more. Visit now and create your account to take full advantage of MeroSpark.

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

Download our Android App from Google Play Store and start reading Reference Notes Offline.

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

Breadth First Search (BFS)
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.
Breadth First Search

BFS Evaluation:


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

Optimal (i.e., admissible):

  • 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 322 times, 1 visits today)

Posted By : Digvijay | Comment RSS | Category : Fifth Semester, Fourth Semester
Tag : ,

Post a Comment

Your email is never published nor shared. Required fields are marked *


Wordpress DMCA
Community | Toolbar | Android App | Founder/Developer : Hari Prasad Chaudhary | CSIT Portal Manager : Digvijay Chaudhary