Depth First Search

Depth First Search

This is a very simple type of brute-force technique. 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 search procedure works the by diving down the tree and one of the children’s children are considered first before considering all the children.

In DFS, instead of generating all the states below the current level, only the first state below the current level is generated and evaluated recursively. The search continues till a further successor cannot be generated or some cut of point is reached (if any). Then it goes back to the parent and explores the next successor (called Backtracking). The algorithm is given below.

• Set initial state to current state, if (initial state is current state) quit
• Else, if (a successor for current state exists) Generate a successor of the current state and set it as current state.
• Else return
• depth_first_search (current_state) ; if (goal state is achieved) return ; else continue ; } }

Figure shows the tree generated by the DFS for the alphabet arrangement problem. The search reached the goal state after evaluating 11 states. Since DFS stores only the states in the current path, it uses much less memory during the search compared to BFS. The probability of arriving at goal state with a fewer number of estimates is higher with DFS compared to BFS. This is because, in BFS, all the states in a level have to be evaluated before states in the lower level are considered. DFS is very efficient when more acceptable solutions exist, so that the search can be terminated once the first acceptable solution is obtained. BFS is advantageous in cases where the tree is very deep. An ideal search mechanism is to combine the advantages of BFS and DFS.