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.