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