优先队列与并行分枝界限算法

Priority Queue and Parallel Branch and bound Algorithms

讨论了分枝界限算法中使用的优先队列结构．针对分枝界限算法的选择规则和淘汰规则，提出了立体堆，双层立体堆，串队列三种新的结构；给出了各结构上相应的基本算法及复杂度分析．在此基础上给出了一类ＰＲＡＭＣＲＥＷ 模型上基于双层立体堆的并行分枝界限算法，其运行时间为Ｏ（（ｒ／ｌｏｇｒ） ｈｌｏｇｈ ＋ ｒｈ） ，其中ｒ 为可用处理器数，ｈ 为找到最优解时的迭代次数．

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.