| 优先队列与并行分枝界限算法 |
| |
| 引用本文： | 武继刚,陈国良.优先队列与并行分枝界限算法[J].烟台大学学报(自然科学与工程版),2000,13(1):45-53. |
| |
| 作者姓名： | 武继刚 陈国良 |
| |
| 作者单位： | 1. 烟台大学,计算机科学与工程系,山东,烟台,264635
2. 国家高性能计算中心,安徽,合肥,230027 |
| |
| 基金项目： | 教育部博士点基金!（9703825） |
| |
| 摘 要： | 讨论了分枝界 使用的优先队列结构，针对分枝 界限算法的选择规则和淘汰规则，提出了立体堆，双层立体堆，串队列三种新的结构；给出了各结构上相应的基本算法及复杂度分析，在此基础上给出了一类ＰＲＡＭ－ＣＲＥＷ模型上基于双层立体堆的并行分枝界限算法，其运行时间为Ｏ（（ｒ／ｌｏｇｒ）ｈｌｏｇｈ＋ｒｈ），其中ｒ为可用处理器ｈ为找到最优解时的迭代次数。
|
| 关 键 词： | 组合搜索 优先队列 分枝界限算法 组合优化 |
Priority Queue and Parallel Branch-and-bound Algorithms |
| |
| WU Ji-gang,CHEN Guo-liang.Priority Queue and Parallel Branch-and-bound Algorithms[J].Journal of Yantai University(Natural Science and Engineering edirion),2000,13(1):45-53. |
| |
| Authors: | WU Ji-gang CHEN Guo-liang |
| |
| Abstract: | The priority queue used in branch?andbound algorithms is discussed in this paper, three data structures called cubeheap, two?levelcubeheap, and string queue, respectively, are presented for the selection rule and the elimination rule. Some fundamental algorithms and their running time on each data structure are proposed. A parallel branch?and?bound algorithm on PRAM?CREW is given based on two?level cubeheap, it runs in O((r /log r)h log h rh ) time with at most r processors, where the h is the number of the iteration when the algorithm finds the first solution of the given problem. |
| |
| Keywords: | Branch and bound combinatorial search priority queue computational complexity parallel algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
