Depth First Search in AI

Depth First Search begins by expanding the initial node by using an operator, It generates all successors of the initial node and tests them. DFS is characterized by the expansion of the most recently generated or deepest node first. It needs to store the path from the root to the leaf node as well as the unexpanded nodes. It is neither complete nor optimal. If DFS goes down an infinite branch will not end till a goal state is found. Even if it is found, there may be a better solution at a higher level.

Depth First Search Algorithm:

Step-1: Put the initial node on a list, START LIST.
Step-2: If(START LIST is empty) or (START LIST=GOAL) then terminate end search.
Step-3: Remove the first node from the START LIST, call this node a.
Step-4: If (a=GOAL) then terminate search with success.
Step-5: Else if node a has successors, generate all of these, and add them at the beginning of START LIST.
Step-6: Go to Step 2.