Bidirectional search, Computer Engineering

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.

Posted Date: 1/9/2013 7:23:12 AM | Location : United States







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

Write discussion on Bidirectional search
Your posts are moderated
Related Questions
Explain the term step-wise refinement. Ans:  Step Wise Refinement  Refinement is a method of elaboration. Here one starts with a statement of function that is described a

How can we use / display table in a screen? ABAP/4 offers two mechanisms for showing and using table data in a screen.  These mechanisms are TABLE CONTROLS and STEP LOOPS.

What is User Defined Functions? User-Defined Functions permit defining its own T-SQL functions that can accept 0 or more parameters and return a single scalar data value or a t

Rhythm Rhythm in art refers to the way that your eye moves through a picture and can be thought of in a similar way to rhythm in music. Your eye will move through some picture

What is a work process? A work process is where individual dialog steps are in fact processed and the work is done.  Every work process ocuurs one type of request.

Question 1: Describe the five maturity levels of KM that an organization faces when adopting the Frid's KM framework. Question 2: (a) Describe three major issues that

Will case infer priority register if yes how give an example? Yes case can infer priority register depending on coding style reg r; // Priority encoded mux, always @

Q. Describe buffer of receiving process? MPI_Gather (Sendaddr, Scount, Sdatatype, Receiveaddr, Rcount, Rdatatype,Rank, Comm): 'Using this function process with rank' rank

Linked list means node which is linked each other with  a line. It means that every node is connected with another one. Every node of the list hold the reference of the next node.

State the data flow diagramming conpects The approach to data flow diagramming is as follows: Create a data flow diagram for each of major outputs of system Work ba