On the Differences and Similarities of fMM and GBFHS

Proceedings of the International Symposium on Combinatorial Search, 13

Volume

Vol. 13 No. 1 (2020): Thirteenth Annual Symposium on Combinatorial Search

Long Papers

fMM and GBFSH are two prominent bidirectional heuristic search algorithms. Over the past few years, there has been a great deal of theoretical and empirical work on both of these algorithms. As part of the research conducted on these algorithms, some interesting theoretical properties were proven for fMM and not for GBFSH and vice versa. In addition, both of them are used as benchmarks for evaluation bidirectional heuristic search algorithms. In this paper we show that fMM infused by a lower-bound propagation and GBFSH are equivalent. In essence, every instance of fMM can be mapped to an instance of GBFSH that expands the exact sequence of nodes and vice versa. This equivalence indicates that all theoretical properties proven for one algorithm hold for both algorithm, and that future analyses and benchmarks can consider only one of these algorithms.

10.1609/socs.v11i1.18536