r (Xi)), where

A technique that has proved useful in shortest path and other discrete optimization computations has been bi-directional search. The method has been well tested in the two-node shortest-path problem providing substantial computational savings. A natural impulse is to extend its benefits to heuristic search. In the uni-directional algorithms, the search proceeds from an initial node forward until the goal node is encountered. Problems for which the goal node is explicitly known can be searched backward from the goal node. An algorithm combining both search directions is bi-directional. This method has not seen much use because book-keeping problems were thought to outweigh the possible search reduction. The use of hashing functions to partition the search space provides a solution to some of these implementation problems.