Minimizing Node Expansions in Bidirectional Search with Consistent Heuristics

摘要: A* is optimally effective with regard to node expansions among unidirectional admissible algorithms—those that only assume the heuristic used admissible. Among bidirectional algorithms Fractional MM algorithm (given correct parameters) algorithms.This paper generalizes result more complex settings where information on problem domain can be exploited: (1) When cost of minimal edge known. (2) knows heuristics are consistent. This characterization uses a novel called MT. MT similar and also effective, but simpler analyze.