Q12Principles of Artificial Intelligence

Depth-First Search (DFS) is a massive, blind, uninformed search algorithm. When navigating a mathematical State-Space Tree, it violently plunges down the absolute deepest, leftmost branch possible. It continues this aggressive dive until it either hits a dead-end (a leaf node) or finds the ultimate goal.

The Algorithmic Execution (LIFO Stack)

• 1. The root node is aggressively pushed onto a Last-In-First-Out (LIFO) Stack data structure.
• 2. The AI violently pops the top node, checks if it is the Goal. If not, it mathematically generates ALL of its children.
• 3. It violently pushes these new children onto the top of the stack.
• 4. Because the stack is LIFO, the AI is mathematically forced to immediately explore the newest, deepest child it just discovered, utterly ignoring the shallower nodes sitting at the bottom of the stack.

Architectural Advantages

Its absolute greatest merit is Memory (Space) Efficiency. Unlike Breadth-First Search (BFS) which must violently store every single node at a given depth (costing exponential RAM, $O(b^d)$), DFS only stores the single path it is currently on and the unexpanded siblings. Its mathematical space complexity is strictly linear: $O(b\times m)$, where $b$ is the branching factor and $m$ is the maximum depth. It can search massive graphs using almost zero RAM.

Architectural Disadvantages

• Not Optimal: It violently grabs the first solution it finds. If a path of length 5 is down the left branch, and a path of length 2 is down the right branch, DFS will output the length 5 path.
• Not Complete: If the graph possesses an infinite loop (e.g., $A\to B\to A$), DFS will plunge into the loop and mathematically hang forever, never finding the goal.