The Minimal Set of States that Must Be Expanded in a Front-to-End Bidirectional Search
The Minimal Set of States that Must Be Expanded in a Front-to-End Bidirectional Search
复制标题
在前端到端双向搜索中必须扩展的最小状态集
DOI：
10.1609/socs.v8i1.18426
复制
发表时间：
2021
影响因子：
3.4
通讯作者：
Nathan R Sturtevant
中科院分区：
文献类型：
--
作者：
E. Shaham;Ariel Felner;Jingwei Chen;Nathan R Sturtevant
在搜索始终如一的启发式时，A*在可允许的单向算法中是最佳的。最近，已经建立了类似的最佳范围用于双向搜索，但是不能保证没有实践算法始终实现这种界限。在本文中，我们研究了必须在任何前后双向搜索中扩展的节点数量的性质。我们提出了一种用于计算该数字的有效算法，并表明具有正确参数的MM的理论参数化概括是最佳的前后双向搜索。然后，我们通过实验比较各种算法，并显示它们离最佳的距离。
A* is optimal among admissible unidirectional algorithms when searching with a consistent heuristic. Recently, similar optimality bounds have been established for bidirectional search, but no practical algorithm is guaranteed to always achieve this bound. In this paper we study the nature of the number of nodes that must be expanded in any front-to-end bidirectional search. We present an efficient algorithm for computing that number and show that a theoretical parameterized generalization of MM, with the correct parameter, is the optimal front-to-end bidirectional search. We then experimentally compare various algorithms and show how far they are from optimal.