Bi-Directional Search

Ph.D. dissertation "Bi-directional and heuristic search in path problems" (Stanford, Computer Science, 1970) summarized in this article in Machine Intelligence 6 (1971).In the uni-directional algorithms, the search proceeds from an initial nodeforward until the goal node is encountered. Problems for which the goal nodeis explicitly known can be searched backward from the goal node. Analgorithm combining both search directions is bi-directional.This method has not seen much use because book-keeping problems werethought to outweigh the possible search reduction. The use of hashingfunctions to partition the search space provides a solution to some of theseimplementation problems. However, a more serious difficulty is involved.To realize significant savings in bi-directional search, the forward andbackward search trees must meet in the 'middle' of the space. The potentialbenefits from this technique motivates this paper's examination of thetheoretical and practical problems in using bi-directional search.