Depth first search (DFS)

This is a very simple type of brute force searching techniques. The search begins by expanding the initial node i.e. by using an operator generate all successors of the initial node and test them.

This procedure finds whether the goal can be reached or not but the path it has to follow has not been mentioned. Diving downward into a tree as quickly as possible performs DFS searches.

Algorithm:

Step1: Put the initial node on a list START.

Step2: If START is empty or START = GOAL terminates search.

Step3: Remove the first node from START. Call this node a.

Step4: If (a= GOAL) terminates search with success.

Step5: Else if node a has successors, generate all of them and add them at the beginning

Of START.

Step6: Go to Step 2.

The major draw back of the DFS is the determination of the depth citric with the search has to proceed this depth is called cut of depth.

The value of cutoff depth is essential because the search will go on and on. If the cutoff depth is smaller solution may not be found. And if cutoff depth is large time complexity will be more.

Advantages:

      DFS requires less memory since only the nodes on the current path are stored.

By chance DFS may find a solution with out examining much of the search space at all.