Depth first search - HiIAmTzeKean/SC3000-Artificial-Intelligence GitHub Wiki

tags:

  • 🌱
  • AI
  • ComputerScience
  • Search date: 18--Apr--2023

Depth first search

  • LIFO stack with backtracking

Cost

  • Complete
    • Finite-depth with no loops: Complete
    • Finite-depth with loops: No, algorithm get trapped in a cycle
      • But if there is a repeat state check it is complete
    • Infinite-depth: No, cannot recover as no backtracking is possible
  • Optimality
    • Cannot guarantee optimal since algorithm only returns the depth first solution which cannot be guaranteed to be optimal one in the state space
  • Time
    • Worse case is the entire space must be explored
    • $O(b^d)$
  • Space
    • Only the frontier nodes will be kept
    • $O(bd)$

Links:

⚠️ **GitHub.com Fallback** ⚠️