Depth First Search or Backtracking Search

Depth First Search or Backtracking Search

Depth first search is a strategy where the nodes are expanded to the deepest level of the search tree.

The searching process in DFS. expands the root node first, then selects a particular successor node and explore in deep until leaf node is reached, It then backup one level and selects the next successor for expansion. Consider the following binary tree.

The above figure shows how DFS algorithm searches the tree to the find goal node '7'

     We can implement depth first search by using GENERAL TREE SEARCH algorithm with last in first out queue i.e., we use stack here instead of a normal FIFO queue.

    Depth first search algorithm requires a storage of bm + 1, where b is the branching factor and m is the maximum depth.

Algorithm

• If the initial state is goal state then quit the search process and return success.
• If the goal state is not reached, repeat the steps mentioned below till success or failure is achieved. 
• Check whether the initial state has any successor.
• If yes, name the successor 'M'.
• If no, return failure.
• Consider 'M' as the initial state and call depth first search procedure for this state.
• If the goal state is reached return success. Otherwise repeat this loop.

Advantages

• Less memory is required, because it stores only the nodes which are on the current path.
• If a problem has different acceptable solutions, then DFS stops the process as soon as any one among the acceptable solutions is obtained.

Disadvantages

• It wastes time in searching each node to the deepest level
• It takes a long path to obtain a solution even if the shorter path is available and unexplored.