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

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.

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

- 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.

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