Description
A Bidirectional Heuristic Search is a state space search from some state to another state, searching from to and from to simultaneously (or quasi-simultaneously if done on a sequential machine). It returns a valid list of operators that if applied to will give us .
While it may seem as though the operators have to be invertible for the reverse search, it is only necessary to be able to find, given any node, the set of parent nodes of such that there exists some valid operator from each of the parent nodes to . This has often been likened to a one way street in the route-finding domain: it is not necessary to be able to travel down both directions, but it is necessary when standing at the end of the street to determine the beginning of the street as a possible route.
Similarly, for those edges that have inverse arcs (i.e. arcs going in both directions) it is not necessary that each direction be of equal cost. The reverse search will always use the inverse cost (i.e. the cost of the arc in the forward direction). More formally, if is a node with parent, then, defined as being the cost from to .(Auer Kaindl 2004)
Read more about this topic: Bidirectional Search
Famous quotes containing the word description:
“The type of fig leaf which each culture employs to cover its social taboos offers a twofold description of its morality. It reveals that certain unacknowledged behavior exists and it suggests the form that such behavior takes.”
—Freda Adler (b. 1934)
“I fancy it must be the quantity of animal food eaten by the English which renders their character insusceptible of civilisation. I suspect it is in their kitchens and not in their churches that their reformation must be worked, and that Missionaries of that description from [France] would avail more than those who should endeavor to tame them by precepts of religion or philosophy.”
—Thomas Jefferson (1743–1826)
“It is possible—indeed possible even according to the old conception of logic—to give in advance a description of all ‘true’ logical propositions. Hence there can never be surprises in logic.”
—Ludwig Wittgenstein (1889–1951)