An Improved Bidirectional Heuristic Search Algorithm

1 April 1977

journal article
Published by Association for Computing Machinery (ACM) in Journal of the ACM

Vol. 24 (2) , 177-191
https://doi.org/10.1145/322003.322004

Abstract

A modification of Pohl's bidirectional heuristic search algorithm is described together with a simplified implementation. Theorems are proved about conditions yielding shortest paths. The results are given of a worst-case analysis of different algorithms, suggesting a rank order of their quality. Results that Pohl had obtained with a unidirectional heuristic search algorithm on the 15-puzzle are compared with the results obtained with the new — simplified — algorithm.

Keywords

DIFFERENT ALGORITHM
ARTIFICIAL INTELLIGENCE
BIDIRECTIONAL HEURISTIC SEARCH ALGORITHM
PATH FINDING
BIDIRECTIONAL HEURISTIC SEARCH
WORST-CASE ANALYSIS
SHORTEST PATH
UNIDIRECTIONAL HEURISTIC SEARCH ALGORITHM
FRONT-TO-FRONT GRADING
IMPROVED BIDIRECTIONAL HEURISTIC SEARCH
RANK ORDER

This publication has 2 references indexed in Scilit:

Look-Ahead and One-Person Games
Journal of Cybernetics, 1972
Bi-Directional and Heuristic Search in Path Problems [Thesis]
Published by Office of Scientific and Technical Information (OSTI) ,1969