Depth-first search Example Advantages and Disadvantages

 

Explain Depth-first search (DFS) with an example. List down the advantages and disadvantages of DFS – Artificial Intelligence

Depth-first search (DFS)

Breadth-First –Search is an uninformed search technique. We may sometimes search the goal along with the largest depth of the tree, and move up only when further traversal along the depth is not possible. We then attempt to find alternative offspring of the parent of the node (state) last visited. If we visit the nodes of a tree using the above principles to search the goal, the traversal made is called depth-first traversal and consequently, the search strategy is called depth-first search

Algorithm: Depth-First Search

1. If the initial state is a goal state, quit and return success. 
 
2. Otherwise, do the following until success or failure is signaled:  
   a) Generate a successor, E, of the initial state. 
      If there are no more successors, signal failure. 
   b) Call Depth-First Search with E as the initial state. 
   a) If success is returned, signal success. Otherwise continue in this loop

Depth-First Search – Example

Let us consider the following tree. Here node ‘A’ is the source or start or initial node and node ‘G’ is the goal node.

Step 1: Initially NODE-LIST contains only one node corresponding to the source state A.

NODE-LIST: A

DFS 1

Step 2: Node A is removed from NODE-LIST. A is expanded and its children B and C are put in front of NODE-LIST.

NODE-LIST: B C

DFS 2

Step 3: Node B is removed from NODE-LIST, and its children D and E are pushed in front of NODE-LIST.

NODE-LIST: D E C

DFS 3

Step 4: Node D is removed from NODE-LIST. C and F are pushed in front of NODE-LIST.

NODE-LIST: C F E C

DFS 4

Step 5: Node C is removed from NODE-LIST. Its child G is pushed in front of NODE-LIST.

NODE-LIST: G F E C

DFS 5

Step 6: Node G is expanded and found to be a goal node.

NODE-LIST: G F E C

DFS 6 Goal State

The solution path A-B-D-C-G is returned and the algorithm terminates.

Advantages of Depth-first search are:

Depth-first search requires less memory since only the nodes on the current path are stored. This contrasts with breadth-first search, where all of the trees that have so far been generated must be stored.

The depth-first search may find a solution without examining much of the search space at all. This contrasts with breadth-first search in which all parts of the tree must be examined to level n before any nodes on level n + i can be examined. This is particularly significant if many acceptable solutions exist. Depth-first search can stop when one of them is found.

Disadvantages of Depth-first search are:

May find a sub-optimal solution (one that is deeper or more costly than the best solution)

Incomplete: without a depth bound, one may not find a solution even if one exists.

Summary

This article discusses depth-first search (DFS) with an example. Also, the advantages and disadvantages of DFS – Artificial Intelligence. If you like the material share it with your friends. Like the Facebook page for regular updates and YouTube channel for video tutorials.

Leave a Comment

Your email address will not be published. Required fields are marked *