10.3969/j.issn.1000-1220.2000.11.007
一类有效的一般并行分枝界限算法
本文针对使用p个处理器选出p个子问题进行并行扩展的一类并行分枝界限算法,提出了一个称作双层立体堆的数据结构,给出了PRAM-CREW模型上的并行分枝界限算法.假定在状态空间树上扩展一个结点最多生成r个子结点,本文提出的并行算法最多使用r个处理器,其运行时间为O((r/logr)hlogh+rh).对于logh<r<h,在系数因子logh/logr的范围内,以及对于logh>r,在系数因子r/logr的范围内,本文提出的并行算法为运行速度最快的算法,其中h为算法找到第一个最优解时所需的迭代次数.
分枝界限、状态空间树、活结点表、并行算法、组合搜索
21
TP301(计算技术、计算机技术)
高等学校博士学科点专项科研项目
2006-02-16(万方平台首次上网日期,不代表论文的发表时间)
共4页
1146-1149