一类有效的一般并行分枝界限算法

本文针对使用 p个处理器选出 p个子问题进行并行扩展的一类并行分枝界限算法 ,提出了一个称作双层立体堆的数据结构 ,给出了 PRAM- CREW模型上的并行分枝界限算法 .假定在状态空间树上扩展一个结点最多生成 r个子结点 ,本文提出的并行算法最多使用 r个处理器 ,其运行时间为 O((r/ logr) hlogh+ rh) .对于 logh <r <h,在系数因子 logh/ logr的范围内 ,以及对于 logh>r,在系数因子 r/ logr的范围内 ,本文提出的并行算法为运行速度最快的算法 ,其中 h为算法找到第一个最优解时所需的迭代次数 .