Breadth first search - artificial intelligence, Basic Computer Science

Breadth First Search - artificial intelligence:

Given a set of operators o1, ..., on in a breadth primary search, every time a new state s is reached, an action for every  operator on s is added to the bottom of the plan, for example  the pairs (s,o1), ..., (s, on) are added to the end of the agenda in that order.

Thus , once the 'D' state had been found, the actions:

1. (empty, add ' N')

2. (empty, add 'A')

3. (empty, add 'D')

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')

we can remove the first agenda item as this action has been undertaken, however .  There are actually  five  actions on the plan after the first step in the search space. Certainly, after each step, one action will be removed (the action just carried out), and 3 will be added, making a total addition of 2 actions to the plan. It turns out that this kind of breadth first search leads to the name 'DAN' after twenty steps. Also, after the 20th step, there are forty three tasks still on the  plan to do.

It's helpful to think of this search as the evolution of a tree, and the diagram below shows how every string of letters is searched from the search in a breadth first manner. The numbers described above the boxes indicate at which step in the search the string was found.

1276_Breadth first search.png

We see that every node leads to3  others, that  corresponds to the fact that after each step, 3 more steps are add on the plan. This is called the branching rate of a search, and seriously affects both how long a search is going to take and how much memory it will utilized in .

Breadth initial search is a full strategy: given enough time and memory, it will find a solution if one exists. Unluckily, memory is a great problem for breadth first search. We may think about how big the plan grows, but in real we are just counting the number of states that are still 'alive', for example , there are still steps in the plan involving them. In the above diagram, the states which are still alive are those with fewer than 3 arrows coming from them: there are fourteen  in all.

It's easy to show that in a search with a branching rate of b, if we want to search all the way to a depth of d, then the biggest number of states the agent will have to store at any one time is bd-1. i.e., if our professor wanted to find for all names up to length eight, she would have to remember (or write down) 2187 different strings to complete a breadth first search. This is because she would have to remember thirty seven strings of length  seven  in order to be able to build all the strings of length  eight from them. In searches with a greater branching rate, the memory requirement may often become too big for an agent's processor.

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







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

Write discussion on Breadth first search - artificial intelligence
Your posts are moderated
Related Questions
Question 1: (a) How would you describe human reasoning? (b) Describe the different types of human reasoning? Question 2: (a) What are the computational factors affec

Question 1 Write a note on modems Question 2 What are the Safe Chatting Rules Question 3 Explain three basic kinds of hypertext links Question 4 Write a no

Question (a) A firm produces four products: P , Q , R , and S . Each unit of product P requires two hours of milling, one hour of assembly, and $10 worth of in-process in


What is methods For handling Deadlocks?

what is operator and operator associatively

Modify the class declaration of the Employee class to specify that the Employee class is an abstract class Declare an abstract method called CalculateNetPay that returns a double v

disvange and advantege of providing intternet sservice to customer

Operating Systems:  An operating system is a set of programs that manage computer hardware resources and provide common services for application software.  There are following kind

Machines which exhibit intelligent nature Machines in this case could easily be personal computers, or they could be robots with embedded systems, or a combination of both. Wh