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.

Depth First Search (DFS) | 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.

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

Depth First Search (DFS)
Looks for the goal node among all the children of the current node before using the sibling of this node i.e. expand deepest unexpanded node.
Depth First Search

DFS Evaluation


  • Does it always find a solution if one exists? :- NO –> If search space is infinite and search space contains loops then DFS may not find solution.

Time complexity;

  • Let m is the maximum depth of the search tree. In the worst case Solution may exist at depth m.
  • root has b successors, each node at the next level has again b successors (total b2), …
  • Worst case; expand all except the last node at depth m
  • Total no. of nodes generated:
    b + b2 + b3 + ………………….. bm = O(bm)

Space complexity:

  • It needs to store only a single path from the root node to a leaf node, along with remaining unexpanded sibling nodes for each node on the path.
  • Total no. of nodes in memory:
    1+ b + b + b + ………………….. b m times = O(bm)

Optimal (i.e., admissible):

  • DFS expand deepest node first, if expands entire let sub-tree even if right sub-tree contains goal nodes at levels 2 or 3. Thus we can say DFS may not always give optimal solution.
(Visited 296 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