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
Data Processing In any computer-based system, data storage and retrieval plays an important role. Data storage involves decision about the encoding of data, assignment o

Given the scenario below, construct a conceptual model. The Seville, Spain soccer association is renovating their soccer arena. They are adding luxury boxes that will be offered to

what is the difference between internet and world wide web?

You are to code a C++ program that will read the file IntList into an integer array. There are no more than 20 integers in the file. After all of the data is read into the file,

create a flowchart showing average score for the 3 quizzes assume that there are 3 sections each having 5 students the only valid number to be entered is 1-100 for the quizzes shou

A Doctor Module Doctor has a list of the patients waiting for consultation. The doctor's module should include all the following details: Fields for common complaint

External interruptions are produced by peripheral devices, for example keyboards, printers, communication cards, etc. They are also produced by coprocessors. It is not achievable t

Our instructor gave us a project in making a mechanical game or simple device using assembly language, can anyone give me a an example of a project description for our proposal?