It is well-known that any admissible unidirectional heuristic search algorithm must expand all states whose $f$-value is smaller than the optimal solution cost when using a consistent heuristic. Such states are called "surely expanded" (s.e.). A recent study characterized s.e. pairs of states for bidirectional search with consistent heuristics: if a pair of states is s.e. then at least one of the two states must be expanded. In this paper, we derive a lower bound, VC, on the minimum possible number of expansions required to cover all s.e. pairs, and present a new admissible front-to-end bidirectional heuristic search algorithm, Near-Optimal Bidirectional Search (NBS), that is guaranteed to do no more than 2VC expansions. We further prove that no front-to-end algorithm has a worst case better than 2VC. Experimental results demonstrate that NBS competes with or outperforms existing bidirectional search algorithms, and often outperforms A* as well.

本文提出了保证做不超过2VC扩展的前沿至末端双向启发式搜索算法，并证明了没有前沿至末端的可接受启发式搜索算法的最差情况比2VC更好。实验结果表明，该算法可以竞争或优于现有的双向搜索算法，通常也优于A*。

前后端双向启发式搜索与近似最优节点扩展