# New Technology

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

## Search This Blog

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