###
DOI:
Journal of Software:2000.11(12):1572-1580

几乎最快与渐近最优的并行分枝界限算法
武继刚,计永昶,陈国良
(烟台大学 计算机系,山东 烟台,264005;中国科学技术大学 计算机科学与工程系,安徽 合肥,230027)
A Nearly Fastest and Asymptotically Optimal General Parallel Branch-and-Bound Algorithm
WU Ji-gang,JI Yong-chang,CHEN Guo-liang
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3155   Download 2724
Received:July 13, 1999    Revised:October 22, 1999
> 中文摘要: 分枝界限算法是求解组合优化问题的技术之一,它被广泛地应用在埃运筹学与组合数学中.对共享存储的最优优先一般并行分枝界限算法给出了运行时间复杂度下界Ω(m/p+hlogp),其中p为可用处理器数,h为扩展的结点数,m为状态空间中的活结点数.通过将共享存器设计成p个立体堆,提出了PRAM-EREW上一个新的一般并行分枝界限算法,理论上证明了对于h<p2p,该算法为最快且渐近最优的并行分枝界限算法.最后对0-r背包问题给出了模拟实验结果.
中文关键词: 枝界限  立体堆  PRAM-EREW  并行算法  组合搜索
Abstract:Branch-and-Bound (B&B) is a problem-solving technique which is widely used for various problems encountered in operations research and combinatorial mathematics. In this paper, the lower bound of running time Ω(m/p+hlogp)(the base of all logarithms in this paper is 2) is presented for general parallel best-first B&B algorithms on shared memory systems, where p is the number of processors available, h is the number of expanded nodes, and m is the total number of active nodes in state-space tree. In addition, a new general parallel best-first B&B algorithm on PRAM-EREW is proposed by devising the shared memory into p cubeheaps. Theoretical analysis shows that it is the fastest algorithm for h<p2p, and it is asymptotically optimal in this type of general parallel B&B algorithms. Computational experiments are conducted to solve 0-r knapsack problem.
文章编号:     中图分类号:    文献标志码:
基金项目:This project is supported by the Ph.D.Fund of the Ministry of Education of China under Grant No.9703825(国家教育部博士点基金). This project is supported by the Ph.D.Fund of the Ministry of Education of China under Grant No.9703825(国家教育部博士点基金).
Foundation items:
Reference text:

武继刚,计永昶,陈国良.几乎最快与渐近最优的并行分枝界限算法.软件学报,2000,11(12):1572-1580

WU Ji-gang,JI Yong-chang,CHEN Guo-liang.A Nearly Fastest and Asymptotically Optimal General Parallel Branch-and-Bound Algorithm.Journal of Software,2000,11(12):1572-1580