Taqi Shah Blogspot

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!