Artificial Intelligence – Depth First Search(DFS)

Okay! So this is my first blog post!

I will start by talking about the most basic solution to search problems, which are an integral part of artificial intelligence.

What the hell are search problems?

In simple language, search problems consist of a graph, a starting node and a goal(also a node). Our aim while solving a search problem is to get a path from the starting node to the goal.

Consider the diagram below, we want to get to the node G starting from the node S.

Which path will we get on solving the search problem? How do we get the path? This is where algorithms come into picture and answer all our questions! We will look at Depth First Search which can be seen as a brute force method of solving a search problem.

Creating the search tree

So how do we simplify this problem? If we reduce the graph structure to a tree(not particularly a binary tree!), the problem would be to find a node with a particular value starting from the root.

So the tree would be as follows:

S will be the root of the tree. S will have children A and G. A will have children B and C. B will have only one child D. C will have children D and G. D will have only one child G.

Now you may ask which ‘D’ will have the child G, the one which is the child of B or the one which is a child of C? The answer is both. We want to consider all the possibilities and thus we have to show all the connections uniquely in the tree.

The diagram below shows the created search tree. Note that the nodes are alphabetically taken from left to right. This will be important later!

Also note that all the leaf nodes are G. This is not because G is the goal, but because there are no edges originating from G. Even if your goal was say D, the search tree would have remained the same.

Depth first search

Now solving the problem is just a matter of generalizing binary tree search to a tree which does not have a fixed number of children in each of its nodes. Depth First Search is quite similar to preorder traversal of a binary tree where you look at the left child, then the node itself and then the right child.

In Depth First Search, there is a priority queue where each element is a path from the root of the tree. The priority of an element is the number of nodes in the path. Higher the number, higher the priority. We use this priority queue in the following algorithm:

Insert the root node into the priority queue
While the queue is not empty
      Dequeue the element with highest priority
      (In case the priorities are same, the alphabetically smaller element is chosen)
      If the path is ending in the goal state, print the path and exit
      Else
            Insert all the children of the dequeued element, into the queue

Now let us apply the algorithm on the above tree and see what it gives us. We will write down the state of the priority queue at each iteration and look at the final output. Each element of the queue is written as [path,priority].

Initialization: { [ S , 1 ] }
Iteration1: { [ S->A , 2 ] , [ S->G , 2 ] }
Iteration2: { [ S->A->B , 3 ] , [ S->A->C , 3 ] , [ S->G , 2 ] }
Iteration3: { [ S->A->B->D , 4 ] , [ S->A->C , 3 ] , [ S->G , 2 ] }
Iteration4: { [ S->A->B->D->G , 5 ] , [ S->A->C , 3 ] , [ S->G , 2 ] }

Iteration5 gives the final output as S->A->B->D->G.

There are many things worth mentioning here:
-> The creation of the search tree is not a part of the algorithm. It is used only for visualization.
-> The algorithm returns the first possible path encountered, it does not search for all possible paths.
-> The returned path is the leftmost possible path in the search tree.

It searches deep into the leftmost branch first, and hence the name Depth First Search.

Because of the above properties, Depth First Search is not favored in not most cases. For example, if we need the shortest path Depth First Search won’t serve our purpose as it will return S->A->B->D->G instead of S->G. This is where Breadth First Search comes into picture. We shall see that in the next post!

Advertisements

6 comments

  1. what is the advantage of using a separate variable ‘priority’ and every time searching for the best priority when we can solve it using a simple stack?

  2. The priority queue is used when there is alphabetical tie-breaking between elements having the same priority. This cannot be done with a stack. For example, if S->A->C comes on top of S->A->B in the stack then you will expand S->A->C first and that won’t give you the leftmost path in the given search tree. If the children of a node are added to the stack keeping in mind the correct alphabetical order then there is no difference in the two methods.

  3. Vaibhav Pandey · · Reply

    Hello Siddhartha……
    I have a question. As you would be knowing, we may also get a search graphs or state space graph which have bidirectional edges, for example in 8/16 puzzle problem. In that situation how search trees will be generated and how BFS or DFS will be performed?

  4. Hi Vaibhav.
    You can choose to ignore the edges which take you back to previously attained states. For example, in the diagram above, if you have an edge from S to A and an edge from A to S, one child of S->A will be S->A->S. You can ignore this child since you have already visited the state S. Also, the nodes shown in the above diagram can be seen as states of the puzzle, where subsequent states are achieved with the help of moves. I hope that answers your question.
    By the way, my name is Siddharth and not Siddhartha.

  5. Ahmed tall · · Reply

    Great, we got an advantage and understood very good.
    Thank you.

  6. Maybe Vaibhav is influenced by the famous novel by Hermann Hesse…

    Great explanation though, Siddharth!
    It is very helpful in addition to the course I’m following at EDX.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: