Current Slide

Small screen detected. You are viewing the mobile version of SlideWiki. If you wish to edit slides you will need to use a larger device.

Depth-First Search

  • Depth-First Search (DFS) begins at the root node and exhaustively search each branch to it maximum depth till a solution is found
    • The successor node is selected going in depth using from right to left (w.r.t. graph representing the search space)
  • If greatest depth is reach with not solution, we backtrack till we find an unexplored branch to follow
  • DFS is not complete
    • If cycles are presented in the graph, DFS will follow these cycles indefinitively
    • If there are no cycles, the algorithm is complete
    • Cycles effects can be limited by imposing a maximal depth of search (still the algorithm is incomplete)
  • DFS is not optimal
    • The first solution is found and not the shortest path to a solution
  • The algorithm can be implemented with a Last In First Out (LIFO) stack or recursion

Speaker notes:

Content Tools

Sources

There are currently no sources for this slide.