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
#to determine whether given year is leap year or not

Debugging Once a program has been written, it has to be tested first to ensure that it is free of errors. It is very normal that any program written will contain mistake

Hello i am a computer science student. now we are going to start our final project. we want to work on Google App Inventor and we want to create mobile application. we are two grou

Brief Define the Phases of Waterfall Model

what is CAI? explain its pitfalls.

For multi-national business IT system, free and open source software (FOSS) is recommended over a proprietary system. The reasons for this recommendation are: 1. Security I

It's a common protocol or "language" computers use to "speak" to each other over the Web.

COMMUNICATION CHANNELS: A wire pair connecting two telephones is the simplest circuit, allowing communication in both directions. Other channels include coaxial cables, optica

In this assignment, you should create a class called ToDoMenu which has a main method that contains the code that implements a command-line menu for managing a collection of ToDoIt

Aim This assignment is intended to assess your skills in understanding and interpreting a moderately complex problem, designing a solution to the problem and implementing the desig