背包问题的最优并行算法

被引：17

作者：

李庆华

李肯立

蒋盛益

张薇

机构：

[1] 国家高性能计算中心(武汉)

[2] 华中科技大学计算机科学与技术学院

来源：

软件学报 | 2003年 / 05期

基金：

国家高性能计算基金;

关键词：

背包问题; NP完全; 并行算法; 分治法;

D O I：

10.13328/j.cnki.jos.2003.05.004

中图分类号：

TN918.1 [理论];

学科分类号：

070104 ;

摘要：

利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法.算法允许使用O(2n/4)1-e个并行处理机单元,0e1,O(2n/2)个存储单元,在O(2n/4(2n/4)e)时间内求解n维背包问题,算法的成本为O(2n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.

引用

页码：891 / 896

页数：6