Parallel Branch-and-Bound Formulations for AND/OR Tree Search
Parallel Branch-and-Bound Formulations for AND/OR Tree Search
复制标题
DOI：
10.1109/tpami.1984.4767600
复制
发表时间：
1984-11
影响因子：
23.6
通讯作者：
Vipin Kumar;L. Kanal
中科院分区：
文献类型：
--
作者：
Vipin Kumar;L. Kanal
本文讨论了两种并行执行分支定界(B&B)搜索的通用方案。这些方案原则上适用于B&B可以解决的大多数问题。这些方案是在SSS*上实现的，SSS*是一种通用算法，在博弈树搜索、结构模式分析和AND/OR图搜索中有应用。在与或树和博弈树搜索的背景下，研究了并行SSS*的性能。文章最后对SSS*的这些并行实现在结构模式分析和游戏中的潜在应用进行了评论。
This paper discusses two general schemes for performing branch-and-bound (B&B) search in parallel. These schemes are applicable in principle to most of the problems which can be solved by B&B. The schemes are implemented for SSS*, a versatile algorithm having applications in game tree search, structural pattern analysis, and AND/OR graph search. The performance of parallel SSS* is studied in the context of AND/OR tree and game tree search. The paper concludes with comments on potential applications of these parallel implementations of SSS* in structural pattern analysis and game playing.