Bi-Directional and Heuristic Search in Path Problems [Thesis]
Ira Pohl, US Atomic Energy Commission (AEC), USDOE · 1969
Path-finding is a key process in many areas of computation. Optimization problems and heuristic search problems are two notable examples. The first part of this dissertation presents a class of algorithms, denoted VGA, for solving the two point shortest path problem in directed graphs with non-negative edge weights. This class is a bi-directional extension of the most efficient kn6wn uni-directional shortest path algorithms. While it has long been realized that bi-directional algorithms often provide computational savings, a theory of this has not been forthcoming until now. This theory shows how a bi-directional method using the proposed cardinality comparison strategy is a priori the best shortest path algorithm within the class of algorithms VGA. These theoretical results are verified by extensive tests of VGA. A computer program was written where several standard uni-directional and bi-directional strategies were compared with cardinality comparison. The program randomly generated a number of large directed graphs and each strategy in turn was tried on numerous path problems within these graphs.