Bidirectional search, Computer Engineering

Assignment Help:

Bidirectional Search:

We've concentrated so far on the searches where the point of view for the search is to find a solution, but not the path to the solution. Like any other searches, we know  and notice the solution, and we know the initial state, but we don't know how to get from one to the other, and the point of view the search is to find a path in the given problem. As in these cases, there in addition to searching forward from the initial state, we can sometimes also search backwards from this kind of problem's solution. This is known as the bidirectional search. 

For example we easily understand, consider the 8-puzzle game in this diagram below, where the main point of the game is just to move the pieces around so by that they are arranged in the right hand diagram. It just that in the search for the solution to this puzzle (the given an arbitrary starting to state); you might start off by moving several of the pieces around to get several of them in their end positions in manner. Then, as you reached closer to the solution state, you might that it work backwards: asking yourself, why and how I can get from the solution to where I am stand at the moment, then reversing the main search path. In this issue yes, you've used a bidirectional search. 

2495_Bidirectional Search.png

Bidirectional search has the main advantage that search can be done in both directions is only required to go for a depth half that is may be of normal searches, and this can often lead to a drastic cut in the number of paths looked at same like this. For this instance, if we were just looking for a path that is come from one town and goes to another through at most six other towns, we can only have to look for the journey through three towns from both directions, we know that which is fairly easy to do, compare to searching all paths through six towns in a normal way of search. 

Unfortunately, it is just often difficult to apply for a bidirectional search because (a) we don't actually sense the solution, only a description of it (b) there may be too many solutions, and we have to choose a few to work backwards from (c) we can't reverse our operators to work backwards from the solution and (d) we have to record all the paths from both sides to check if any two meet at the same point  - this may take up a lot of memory, and considering through both sets repeatedly could take up more computing time.


Related Discussions:- Bidirectional search

C, Write a program to find the area under the curve y = f(x) between x = a ...

Write a program to find the area under the curve y = f(x) between x = a and x = b, integrate y = f(x) between the limits of a and b. The area under a curve between two points can b

I have a user defined function that does not recalculate, Contain all the c...

Contain all the cells that your UDF depends on in the argument list. Or enter this as the first statement in your Function: Application.Volatile This will cause the functi

Explain the working of a hybrid in telephone networks, How does a hybrid in...

How does a hybrid in telephone networks work ? The circuit operation is as follows: The input signal is coupled to the B and F windings similarly. By the C winding, the i

What is the advantage of dividing an email address, What is the advantage o...

What is the advantage of dividing an email address into two parts? The division of an e-mail address in two parts is significant since it achieve two objectives. First, the div

Explain the structured design of system, Q. Explain the Structured Design o...

Q. Explain the Structured Design of system? Structured Design utilizes graphic description (Output of system analysis) and focuses on development of software specifications.

Explain conditions under which a deadlock situation arise, What are conditi...

What are conditions under which a deadlock situation may arise? A deadlock situation can arise if the following four conditions hold concurrently in a system:  a. Mutual exc

Dynamic partitioning - computer architecture, Dynamic partitioning: To...

Dynamic partitioning: To rise above from difficulties with fixed partitioning, partitioning can be done dynamically, which called dynamic partitioning. Having it, the primary

Loop level-parallelism based on granularity size, Loop Level This is...

Loop Level This is one more level of parallelism where iterative loop instructions can be parallelized. Fine Granularity  size is used at this level also. Simple loops in a

Illustrate what is pascal''s principle, Illustrate what is pascal's princip...

Illustrate what is pascal's principle? Answer:- Pascal's Principle declares that the pressure is transmitted evenly through a liquid. That's why when you pump up a balloon

Define about pascaline - mechanical computers, Pascaline:Mechanical compute...

Pascaline:Mechanical computers Blaise Pascal made the initial attempt in the direction of this automatic computing. He invented a apparatus, which comprised of lots of gears an

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd