Depth first search-artificial intelligence, Basic Computer Science

Depth First Search-Artificial intelligence:

Depth first search is  similar to breadth first, except that things are added to the top of the plan rather than the bottom. In our example, the first 3 things o n the agenda would still be:

Hence, once the 'D' state had been searched , the actions:

1. (empty, add'N')

2. (empty, add'D')

3. (empty, add 'A')

Would be added to the top of the plan, so it would look like this:

4. ('D', add 'D')

5. ('D', add 'A')

6. ('D', add 'N')

Certainly, carrying out the action at the top of the plan  would introduce the string 'DD', but then this would cause the action:

('DD', add 'D')

to be added to the top, and the next string searched  would be 'DDD'. Obviously, this can go on definitely, and in practice, we might specify a depth bound to stop it going down a particular path forever. That is, our agent will have  to record how far down a specific  path it has gone, and avoid putting actions on the plan if the state in the agenda item is past a certain

Notice that our search for names is special: no matter what state we reach, there will always be 3 actions to put to the plan. In other searches, the number of actions available to undertake on a particular state may be 0 that effectively stops that branch of the search. perhaps, a depth limit is not always required.

Back to our example, if the professor stipulated that she wanted very short names (of three or fewer letters), then the search tree would appear like this.

 

875_Depth first search.png

 

We see that 'DAN' has been reached after the 12th step, so there is an improvement on the breadth first search. Whether, in this case, it was fortunate that the first letter explored is 'D' and that there is a solution at depth 3. If the depth limit had been set at four  instead, the tree would have looked very  different.

 

284_Depth first search1.png

 

It seem like it will be a long time until it finds 'DAN'. This highlights an essential drawback to depth first search. It may often go deep down paths which have no solutions, when there is a solution much higher up the tree, but on a another branch. Also depth first search is not complete, in general.

Rather than just adding the next planed  item directly to the top of the agenda, it might be a good  idea to make sure that every and each  node in the tree is fully expanded before moving on to the following  depth in the search. This is the kind of depth first search which and Norvig and Russell's explain. For our DNA example, if we did this, the search tree would seem like this:

 

1898_Depth first search2.png

The great advantage to depth first search is that it requires much less memory to operate than breadth first search. If we count the number of 'alive' nodes in the above diagram, it amounts to only four, because the ones on the bottom row are not to be expanded due to the depth boundary Indeed, it may be shown that if an agent wants to find  for all solutions up to a depth of d in a space with branching factor b, then in a depth first search it only have  to remember up to a utmost of d*b states at any 1 time.

To put this in perspective, if our professor wanted to find  for every  names up to length eight , she would  have to remember 8*3 = 24 different strings to complete a depth first search (rather than 2187 in a breadth first search).

Posted Date: 10/2/2012 2:14:11 AM | Location : United States







Related Discussions:- Depth first search-artificial intelligence, Assignment Help, Ask Question on Depth first search-artificial intelligence, Get Answer, Expert's Help, Depth first search-artificial intelligence Discussions

Write discussion on Depth first search-artificial intelligence
Your posts are moderated
Related Questions
I am using block matching algorithm to get the motion vectors, now, how can I get the depth map/depth value from the motion vectors?

what is the goals of enterprise collaboration system?

Find the corresponding matrix of the digraph above

Problem 1 Research designs have a critical and directive role to play in the research process. Explain the meaning of research design. Describe the various types of research de

History of E-mail: Internet based E-mail system was designed by a Computer engineer - Ray Tomlinson in late 1971 while working with ARPANET. Tomlinson used a file transfer pro

Write an Assembly program that reads an integer (-32,768 through 32,767) in decimal and prints its equivalent in binary. The output must show all 16 bits. And you must use a loop


Computer Help Inc. is a computer timesharing, and software development and sales company. It has been successful in attracting clients for both sides of its business. Staff count

Browser Security: WWW is used for many applications today including Banking, reservation, trading,  e-commence and many such applications which require security and confidenti

Padovan sequence