MM: A bidirectional search algorithm that is guaranteed to meet in the middle

摘要: Abstract Bidirectional search algorithms interleave two separate searches, a normal forward from the start state, and backward goal. It is well known that adding heuristic to unidirectional dramatically reduces effort. By contrast, despite decades of research, bidirectional has not yet had major impact. Additionally, no comprehensive theory was ever devised understand nature search. In this paper we aim close gap. We first present MM , novel algorithm. Unlike previous algorithms, 's searches are guaranteed “meet in middle”, i.e. never expand node beyond solution midpoint. Based on unique attribute framework for comparing A*, their brute-force variants. do by dividing entire state space into disjoint regions based distance This allows us perform comparison these per region basis identify conditions favoring each Finally, experimental results support our theoretical analysis.