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 next Augustan age will dawn on the other side of the Atlantic. There will, perhaps, be a Thucydides at Boston, a Xenophon at New York, and, in time, a Virgil at Mexico, and a Newton at Peru. At last, some curious traveller from Lima will visit England and give a description of the ruins of St Paul’s, like the editions of Balbec and Palmyra.”
—Horace Walpole (1717–1797)
“The great object in life is Sensation—to feel that we exist, even though in pain; it is this “craving void” which drives us to gaming, to battle, to travel, to intemperate but keenly felt pursuits of every description whose principal attraction is the agitation inseparable from their accomplishment.”
—George Gordon Noel Byron (1788–1824)
“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)