שחף שפרברג

FMM and GBFHS are two prominent parametric bidirectional heuristic search algorithms. A great deal of theoretical and empirical work has been done on both of these algorithms over the past few years. A number of interesting theoretical properties were proved for only one of these algorithms. In this paper we analyze the differences and similarities between these algorithms by comparing their minimal number of node expansions, and their implementations. Importantly, we introduce a version of fMM, called dfMM, that uses a dynamic fraction, and show that when both algorithms are enriched by lower-bound propagation they become equivalent. In particular, for every parameter value of dfMMlb we provide a parameter value of GBFHSlb such that both algorithms expand the same sequence of nodes, and vice versa. This equivalence indicates that all theoretical properties proved for one algorithm hold for both. Therefore, it suffice to consider only one of these algorithms for future analyses and benchmarks.