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

武继刚1计永昶2陈国良2

1.烟台大学; 2.中国科学技术大学;

摘要：

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

关键词：分枝界限、立体堆、PRAM-EREW、并行算法、组合搜索

所属期刊栏目：11

分类号：TP301(计算技术、计算机技术)

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

页数：共9页

页码：1572-1580