并行分枝界限搜索的实用数据结构及算法

摘要

该文给出了分枝界限搜索算法的复杂度下界，提出了一种称作串队列的数据结构，能方便地实现分枝界限搜索中的选择规则与淘汰规则。在ＰＲＡＭ－ＣＲＥＷ模型上提出了一个并行分枝界限算法，其运行时间为Ｏ（ｍ／Ｐ＋ｈ（ｌｏｇｈ＋ｌｏｇｐ））。