论文部分内容阅读
本文针对使用ｐ个处理器选出ｐ个子问题进行并行扩展的一类并行分枝界限算法，提出了一个称作双层立体堆的数据结构，给出了ＰＲＡＭ－ＣＲＥＷ模型上的并行分枝界限算法。假定在状态空间树上扩展一个结点最多生成ｒ个子结点，本文提出的并行算法最多使用ｒ个处理器，其运行时间为Ｏ（（ｒ／ｌｏｇｒ）ｈｌｏｇｈ＋ｒｈ）。对于ｌｏｇｈ〈ｒ〈ｈ，在系数因子ｌｏｇｈ／ｌｏｇｒ的范围内，以及对于ｌｏｇｈ〉ｒ，在系数因子ｒ／ｌｏｇ