D

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
SEE THE SOURCES USED FOR THE GLOSSARY DEFINITIONS HERE
A uninformed search strategy that always expands the deepest node in the current frontier of the search tree. The frontier is implemented as a LIFO queue. It is complete in finite state spaces when a closed list is used. It is not optimal, but has linear space complexity. Explored nodes with no descendants in the frontier are removed from memory.

DEPTH-FIRST SEARCH ALGORITHM

node ← create node with        
       STATE = problem.INITIAL-STATE, 
       PATH-COST = 0, 
       DEPTH = 0
frontier ← create LIFO queue
frontier.INSERT(node)
closed-list ← create empty set

WHILE NOT (frontier.EMPTY)     
      node ← frontier.POP()
      IF problem.GOAL-TEST(node.STATE) THEN
         return node as solution
      closed-list.ADD(node.STATE)
      
      // NODE EXPANSION     
      FOR EACH operator IN problem.LEGAL-OPERATORS(node.STATE)
          successor ← problem.APPLY(operator, node.STATE)
          IF NOT successor in closed-list THEN
             // NODE GENERATION
             child ← create node with
                     STATE = successor,
                     PARENT = node,
                     ACTION = action represented by operator,
                     PATH-COST = node.PATH-COST + 
                                 problem.COST(ACTION, node.STATE)
                     DEPTH = node.DEPTH + 1                  
          
             IF successor in frontier THEN
                frontier.REMOVE(node with STATE == successor)
             frontier.INSERT(child)
      END
END
return failure
SEE example with fragment of the Travel Through Switzerland problem HERE
A variant of depth-first search created to alleviate its failure in infinite state spaces. The search is provided with a predetermined depth limit l, and nodes at depth l are treated as if they have no successors.