Depth First Search (DFS): DFS expands the leaf node with the highest path cost so far, and keeps going until a goal node is generated. If the path cost simply equals the number of links, we can implement this as a simple stack (“last in, first out”).
This is not guaranteed to find any path to a goal state. It is memory efficient even if the state space is large. If the typical branching factor is b, and the maximum depth of the tree is m – the space complexity is O(bm), and the time complexity is O(b^m).
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.
Then it goes back to the parent and explores the next successor. The algorithm is given below.
depth_first_search ()
{
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 ;
}
} 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 evaluations 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.
