Single-frontier bidirectional search

摘要: On the surface, bidirectional search (BDS) is an attractive idea with potential for significant asymptotic reductions in effort. However, results practice often fall far short of expectations. We introduce a new algorithm, Single-Frontier Bidirectional Search (SF-BDS). Unlike traditional BDS which keeps two frontiers, SF-BDS uses single frontier. Each node tree can be seen as independent task finding shortest path between current start and goal. At particular we decide to from goal or start, choosing direction highest minimizing total work done. Theoretical give insights when this approach will experimental data validates algorithm broad range domains.