Breadth First Search (BFS)| Fourth Semester | Cognitive Science | BSc.CSIT (TU)

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

Breadth First SearchBreadth First Search (BFS) | Fourth Semester
Second Year | Tribhuvan University (TU)
Subject: Cognitive Science | 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:

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)

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

Posted By : Digvijay | Comment RSS | Category : 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