几乎最快与渐近最优的并行分枝界限算法

• 作者: 武继刚 计永昶 陈国良
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 分枝界限 立体堆 PRAM-EREW 并行算法 组合搜索
• 年，卷（期）: 2000,（12）
• 页码范围: 1572-1580
• 页数: 9页
• 分类号: TP301
• 字数: 1282字
• 语种: 中文

摘要

分枝界限算法是求解组合优化问题的技术之一,它被广泛地应用在埃运筹学与组合数学中.对共享存储的最优优先一般并行分枝界限算法给出了运行时间复杂度下界Ω(m/p+hlogp),其中p为可用处理器数,h为扩展的结点数,m为状态空间中的活结点数.通过将共享存器设计成p个立体堆,提出了PRAM-EREW上一个新的一般并行分枝界限算法,理论上证明了对于h<p2p,该算法为最快且渐近最优的并行分枝界限算法.最后对0-r背包问题给出了模拟实验结果.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈国良	中国科学技术大学计算机科学与工程系	123	2142	20.0	43.0
2	武继刚	烟台大学计算机系	4	3	1.0	1.0
6	计永昶	中国科学技术大学计算机科学与工程系	2	7	1.0	2.0