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

武继刚; 陈国良

doi:10.13951/j.cnki.37-1213/n.2000.01.010

烟台大学学报（自然科学与工程版） ›› 2000, Vol. 13 ›› Issue (1) : 45 -53. DOI: 10.13951/j.cnki.37-1213/n.2000.01.010

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

武继刚,陈国良

作者信息 +

Author information +

文章历史 +

摘要

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