背包问题的最优并行算法

• 作者: 张薇 李庆华 李肯立 蒋盛益
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 背包问题 NP完全 并行算法 分治法
• 年，卷（期）: 2003,（5）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 891-896
• 页数: 6页
• 分类号: TP301
• 字数: 5508字
• 语种: 中文

摘要

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