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

摘要：

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

关键词： 分枝界限 活节点表 PRAM-CREW 并行算法 组合探索

作者: 武继刚 张宪超 陈国良

作者单位: 大学计算机系 科学技术大学计算机系

会议类型: 国内会议

会议名称: 1999年全国理论计算机科学学术年会

会议地点: 浙江金华

会议语种:中文

页码: 37～42

在线出版日期: 1999-10-01（万方平台首次上网日期，不代表论文的发表时间）