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
ANALOGUE COMPUTERS A computer is basically a problem-solving device. In aircraft radio systems the problem to be solved is concerned with navigation, in that given certain inf

AsBased on Chapter Review Problems from the book. 1 #1. What is meant by data independence? Explain your answer. #2. Identify two benefits of separating application software fr

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

Question 1 Convert the following hexadecimal numbers to base 2 (D73)16 (A21)16 Question 2 Convert the following binary numbers to base 16 (11001011)2 (11

Problem 1 What are graphic applications? Explanation of different graphics applications Problem 2 Open the case cover of your CPU of your computer system and l

what does it means

Question 1 Write short note on                             1) NFS 2) CIFS Question 2 What is Virtual Application? Write down the benefits and drawbacks of it Questi

Ask qu The figure below shows a rooted tree, 756_Find the height.png 1.1. Find the height/level of the tree as shown above?estion #Minimum 100 words accepted#

General Considerations for Search If we can specify the first state, the operators and the goal check for a look for difficulty, then we know where to create, how to move and w

QUESTION 1 Describe the binary search algorithm using an example of your own. QUESTION 2 (a) By showing all your workings, give a big-O estimate for f(x) = (x + 1)lo