| 几乎最快与渐近最优的并行分枝界限算法 |
| |
| 引用本文： | 武继刚,计永昶,陈国良.几乎最快与渐近最优的并行分枝界限算法[J].软件学报,2000,11(12):1572-1580. |
| |
| 作者姓名： | 武继刚 计永昶 陈国良 |
| |
| 作者单位： | 1. 烟台大学,计算机系,山东,烟台,264005;中国科学技术大学,计算机科学与工程系,安徽,合肥,230027
2. 中国科学技术大学,计算机科学与工程系,安徽,合肥,230027 |
| |
| 基金项目： | This project is supported by the Ph.D.Fund of the Ministry of Education of China under Grant No.9703825(国家教育部博士点基金）. |
| |
| 摘 要： | 分枝界限算法是求解组合优化问题的技术之一，它被广泛地应用在埃运筹学与组合数学中.对共享存储的最优优先一般并行分枝界限算法给出了运行时间复杂度下界Ω(m/p+hlogp),其中p为可用处理器数，h为扩展的结点数，m为状态空间中的活结点数.通过将共享存器设计成p个立体堆，提出了PRAM-EREW上一个新的一般并行分枝界限算法，理论上证明了对于h<p2p，该算法为最快且渐近最优的并行分枝界限算法.最后对0-r背包问题给出了模拟实验结果.
|
| 关 键 词： | 枝界限 立体堆 PRAM-EREW 并行算法 组合搜索 |
| 收稿时间： | 1999/7/13 0:00:00 |
| 修稿时间： | 1999/10/22 0:00:00 |
A Nearly Fastest and Asymptotically Optimal General Parallel Branch-and-Bound Algorithm |
| |
| WU Ji-gang,JI Yong-chang and CHEN Guo-liang.A Nearly Fastest and Asymptotically Optimal General Parallel Branch-and-Bound Algorithm[J].Journal of Software,2000,11(12):1572-1580. |
| |
| Authors: | WU Ji-gang JI Yong-chang and CHEN Guo-liang |
| |
| 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
|
| |
| Keywords: | branch-and-bound cubeheap PRAM-EREW parallel algorithm combinatorial search |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
