Bidirectional search-artificial intelligence, Basic Computer Science

Bidirectional Search-Artificial intelligence:

We've concentrated so far on searches where the point of the search is to search a solution, not the path to the solution. In another search, we know the solution, and we know the first state, but we don't know how to get from one to the other, and the point of the search is to search a path. In these cases, in addition to searching forward from the first state, we may sometimes also search backwards from the solution. This is known a bidirectional search.

For example, suppose the 8-puzzle game in the diagram below, where the point of the game is to move the pieces around so that they are set in the right hand diagram. It's likely that in the search for the solution to this puzzle (given an arbitrary starting state), you must start off by moving some of the pieces around to get some of them in their end positions. Then, as you got nearer to the solution state, you must work backwards: by asking yourself, how can I get from the solution to where I am at the moment, then reversing the seek path. In this type of case, you've used a bidirectional search.

128_Bidirectional Search.png

Bidirectional search has the advantage that search conduct in both directions is only required to go to a depth half that of usual searches, and this may often lead to a strong reduction in the number of paths looked at. For example, if we were searching for a path from one town to other through at mainly six other towns, we only need to look for a journey through 3 towns from both directions, which is easy to do, compare to searching every paths through 6 towns in a normal search.

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







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

Write discussion on Bidirectional search-artificial intelligence
Your posts are moderated
Related Questions
Problem 1. Explain the different categories of instructions. Explanation of 4 categories 2. Explain the steps to be followed for the addition of floating point numb

What is new? ERP, on the other hand begins with a fresh relook at the existing business. In fact it is the result of a happy marriage between Business Process Reengineering (BP

Telecommunications network: "A telecommunications network, at its simplest, may be regarded as comprising a transmission network, an arrangement of transmission paths and swit

Login Because the information on a network is sharable, networks are very susceptible to unauthorized intruders. In order to prevent unauthorized access to use the services o

Optical Mark Recognition (OMR): OMR is the scanning of paper to detect the presence or absence of a mark in a predetermined position. Now days, it is used as an input device f

Question 1 What are the various steps involved in pre-production design? Question 2 What are the different kinds of perspectives used in a layout? Question 3 Descr

Computer Storage: Computer systems include two types of digital information storage: internal storage, within the CPU, and the backing (back up) storage on external devices su

Computer as a Data Processor: The main function of a computer is to process the input data according to a specific program to produce the desired output. This is the reason wh

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

Given the following grammar: -> [ , ] | -> | { } -> a | b | cwhich are the strings generated by the grammar? Show the parse tree(s). a). { [ a , b ] }b). [ { a } , b ]