Bidirectional Heuristic Search: Expanding Nodes by a Lower Bound
Bidirectional Heuristic Search: Expanding Nodes by a Lower Bound
复制标题
双向启发式搜索：按下界扩展节点
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Avi Hayoun
中科院分区：
文献类型：
--
作者：
Shahaf S. Shperberg;Ariel Felner;Nathan R Sturtevant;S. E. Shimony;Avi Hayoun
最近的双向搜索工作定义了一个下界的节点对之间的路径的成本，并介绍了一种新的算法，NBS，这是基于这个界。基于这些结果，我们引入DVCBS，一个新的算法，旨在进一步减少扩展的数量。推广超出特定的算法，然后，我们提出了一种方法，通过传播这样的边界之间的下限（LB传播），以提高quantistics。这种lb传播可以用于现有的算法，通常可以提高它们的性能，并使它们“表现良好”。
Recent work on bidirectional search defined a lower bound on costs of paths between pairs of nodes, and introduced a new algorithm, NBS, which is based on this bound. Building on these results, we introduce DVCBS, a new algorithm that aims to to further reduce the number of expansions. Generalizing beyond specific algorithms, we then propose a method for enhancing heuristics by propagating such lower bounds (lb-propagation) between frontiers. This lb-propagation can be used in existing algorithms, often improving their performance, as well as making them "well behaved".