Bi-Directional and Heuristic Search in Path Problems [Thesis]

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 known uni-directional shortest path algorithms. While it has long been realized that hi-directional algorithms often provide computational savings, a theory of this has not been forthcoming until now. This theory shows how a hi-directional method using the proposed cardinal@ 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. In heuristic search for artificial intelligence problems, algorithms similar to the two point shortest path problem are used. The spaces searched are enormous , often infinite, and in consequence the constraint on finding the shortest path is abandoned. The concern is for finding any solution path with minimum effort. The second part of the dissertation presents a theory of these problems and some experiments with the fifteen puzzle in using the methods suggested by this theory of heuristic search. The evaluation function directing the search is the sum of the distance from the starting node and an estimate of the distance to the goal. This second component is the heuristic term, and if accurate, allows efficient path finding in-iii-large spaces. Some results on the effect of error in the heuristic term are presented. Especially interesting is theorem '7.9, showing that the distance from the start should be incorporated in the evaluation function. This particular result runs counter to the reliance strictly on the heuristic term, a practice which is widespread. Bi-directional heuristic search is also proposed. VGHA, a bi-directional class of algorithms, is an extension of the Hart, Nilsson, and Raphael uni-directional heuristic search algorithms. Their results are extended to this more general class. These methods are used in solving fifteen puzzle problems and comparing the number of nodes explored. It is a continuance of the empirical work started by Doran and Michie with the …