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
Question 1 What is Content Addressable Storage? Explain the elements of Content Addressable Storage Question 2 Explain briefly about DAS Question 3 Explain about N

The elif statement permits you to check multiple expressions for truth value and execute a block of code the moment one of the conditions estimates to true. similar to the else, th

explain the steps to form a colourful card

The term ‘page traffic’ describes

7. Name and explain the action in Conceptual Dependency which refers to a transfer of possession.

what is input and output device? explain meaning of input and output devices

Because it is enormously low level, assembly language can be optimized enormously well. Therefore assembly language is used where the extreme performance is needed for applications

1. In discussing software algorithms for mutual exclusion, we noted that optimizing compilers and out-of-order execution by processors could invalidate most of these algorithms bec

Sometimes you may drop to perform conversions among the built-in types. To translate between types you just use the type name as a function. There are quite a few built-in function

TYPES OF PC:  In general,  basic function of all the computers is same i.e. Computers accept data as input, perform operations on these data and generates the desired output t