Trending Technology Machine Learning, Artificial Intelligent, Block Chain, IoT, DevOps, Data Science

Recent Post

Codecademy Code Foundations

Search This Blog

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

     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.

No comments:

Post a Comment

Popular Articles