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
Given an operating system that supports a one – to –one relationship between user-level threads and kernel – level threads and allows one or more threads from a process to issue b

Need of operating system: What kind of facilities operating system provides to the users and programs: The operating system provides interfaces for the user (keyboard, m

Question 1 Explain different functions of an operating system. Explain the evolution of operating systems Question 2 Explain process creation and process termination Ques

Library function :   These are the functions supplied with the programming language. The code or definition of library functions does not have to be written in a user program w

different types of software interfaces which falls in different categories

Input unit: These are used to read data and transfer to primary memory contained in CPU through keyboard or floppy disk or mouse etc. Central Processing Unit (CPU): This consists o

A car battery is of 12 V. Eight dry cells of 1.5 V each connected in series can give 12 V. But such cells are not used in starting a car. Why?


One of the first caveats programmers come across when learning Python is the reality that there are no braces to point to blocks of code for class and function definitions or flow

Problem 1. What are Micro-operations? Explain Micro operations of the Fetch cycle. Defining Micro-operations Its explanation of the fetch cycle 2. Differen