Depth-first search (DFS)

Explore only one branch deeper till the solution is found or there is no new state to explore and then start searching the adjacent level.

This technique is called depth first search (DFS).

By chance the solution exists in the first branch then depth search can find the solution quickly.

If the solution exists in some other branches farther away, there won't be much difference between depth first search and breadth first search.

Expand deepest unexpanded node

Implementation:

A depth-first search (DFS) explores a path all the way to a leaf before backtracking and exploring another path.

For examples, after searching A, then B, then D, the search backtracks and tries another path from B.

Node are explored in the order A B C D E H L M N I O P C F G J K Q.

N will be found before.

The depth-first search Algorithm:-

begin

open := [Start]; % initialize

closed := [];

while open ≠ [] do % states remain

begin

remove leftmost state from open, call it X;

if X is a goal then returns SUCCESS % goal found

else begin

generate children of X;

put X on closed;

discard children of X if already on open or closed; % loop check

put remaining children on left end of open % stack

end

return FAIL % no states left

end.

A trace of depth-first Algorithm :-

1. open = [A]; closed = [ ]

2. open = [B,C,D]; closed = [A]

3. open = [E,F,C,D]; closed = [B,A]

4. open = [K,L,F,C,D]; closed = [E,B,A]

5. open = [S,L,F,C,D]; closed = [K,E,B,A]

6. open = [L,F,C,D]; closed = [S,K,E.B,A]

7. open = [T,F,C,D]; closed = [L,S,K,E,B,A]

8. open = [F,C,D]; closed = [T,L,S,K,E,B,A]

9. open = [M,C,D], as L is already on closed; closed = [F,T,L,S,K,E,B,A]

10. open = [C,D]; closed = [M,F,T,L,S,K,E,B,A]

11. open = [G,H,D]; closed = [C,M,F,T,L,S,K,E,B,A]

Properties of depth-first search

Complete? No: fails in infinite-depth spaces, spaces with loops

- Modify to avoid repeated states along path

→ complete in finite spaces

Time? O(bm): terrible if m is much larger than d

- but if solutions are dense, may be much faster than breadth-first

Space? O(bm), i.e., linear space !

Optimal? No

Depth-first search sample

Branching factor :- number of nodes generated by a node parent (we called here "b")

⇒ Here after b = 2

Depth First Complexity

Let b: is the branching factor
Let d: maximum depth to find solution
So, the maximum number of nodes expended before finding a solution at level "m".
Complexity in best case = O(b*d) which is excellent!.

Time and memory requirement in Depth-first

Comparing the ordering of search sequence

- Determine the order of nodes (states) to be examine
- Breadth-first search
    - When a state is examined, all of its children are examined, one after another
    - Explore the search space in a level-by-level fashion
Depth-first search
    - When a state is examined, all of its children and their descendants are examined before any of its siblings
    - Go deeper into the search space whee possible.