Bidirectional heuristic search reconsidered

摘要: The assessment of bidirectional heuristic search has been incorrect since it was first published more than a quarter century ago. For quite long time, this strategy did not achieve the expected results, and there major misunderstanding about reasons behind it. Although is still wide-spread belief that afflicted by problem frontiers passing each other, we demonstrate conjecture wrong. Based on finding, present both new generic approach to dynamically improving values feasible in only. These approaches are put into perspective with traditional recently proposed order facilitate better overall understanding. Empirical results experiments our show can be performed very efficiently also limited memory. suggest appears for solving certain difficult problems corresponding unidirectional search. This provides some evidence usefulness neglected. In summary, viable consequently propose reconsidered.