基于分治思想0-1背包问题的并行算法研究

论文摘要

0-1背包问题是一种经典的NP难问题，目前还无法找到线性时间内求解该问题的算法，由于求解0-1背包问题在优化组合、资本预算、货物装载、削减库存以及信息密码学等领域具有极为重要的应用，因此，降低求解该类问题的计算成本具有重大的理论和现实意义，并引起了各国学者的极大重视。随着并行计算技术的逐步成熟，人们将求解0-1背包问题的重点转向并行算法的研究，当前解决0-1背包问题的并行算法主要分为动态规划法和分治法两种思路，其中动态规划法已经成功运用到了0-1背包问题的并行算法中，并已经涌现出大量的研究成果。不过至今为止分治法主要运用到求解子集和问题中，而基于分治思想设计求解0-1背包问题的并行算法并没有引起同样的关注。因此，在深入研究了PRAM并行计算模型和并行分治思想后，本文给出了求解0-1背包问题的串行二表算法和串行三表算法，并创新性的提出了两种基于EREW PRAM模型求解0-1背包问题的并行算法即并行三表算法和并行二表算法，并对算法进行理论上的性能分析和比较，其中并行三表算法比并行二表算法占用较少的储存空间，而并行二表算法则是迄今为止求解0-1背包问题算法性能分析中，仅考虑背包物品规模这一个因素成本最优且完全避免内存访问冲突的并行算法。最后，本文分别基于OpenMP和MPI+OpenMP编程模型对0-1背包问题并行二表算法进行了编程实验，并对实验进行反复测试，从而比较了不同多核平台环境下并行程序运行时间的差异以便分析并行算法的性能。实验结果很好的证明了基于OpenMP编程模型并行二表程序在减少程序运行时间方面的可行性，且程序表现出较好的加速比和并行效率。

论文目录

• 摘要
• Abstract
• 目录
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 课题的研究背景与意义
• 1.2 国内外研究水平与现状
• 1.3 论文主要工作
• 1.4 论文创新点及主要贡献
• 1.5 论文组织结构
• 1.6 小结
• 第2章 并行计算机模型及并行程序设计
• 2.1 并行计算
• 2.1.1 并行计算机模型
• 2.1.2 并行求解模型
• 2.2 并行编程语言
• 2.2.1 基于共享存储结构的 OpenMP 并行编程
• 2.2.2 基于消息传递的 MPI 并行编程
• 2.3 并行算法的性能评价
• 2.4 小结
• 第3章 0-1 背包问题并行三表算法设计
• 3.1 串行三表算法设计
• 3.2 最优归并算法
• 3.3 并行三表算法思想与算法设计
• 3.3.1 生成阶段
• 3.3.2 求块内最值阶段
• 3.3.3 剪块阶段
• 3.3.4 搜索阶段
• 3.4 算法性能分析
• 3.5 小结
• 第4章 0-1 背包问题并行二表算法设计
• 4.1 串行二表算法设计
• 4.2 并行二表算法思想与算法设计
• 4.2.1 生成阶段
• 4.2.2 求块内最值阶段
• 4.2.3 剪块阶段
• 4.2.4 搜索阶段
• 4.3 并行二表算法处理机数目的自适应
• 4.4 算法性能分析与比较
• 4.4.1 算法性能分析
• 4.4.2 算法性能比较
• 4.5 小结
• 第5章 0-1 背包问题并行二表算法程序实验
• 5.1 基于 MPI+OpenMP 模型 0-1 背包问题并行二表程序
• 5.1.1 MPI+OpenMP 混合模型
• 5.1.2 基于 MPI+OpenMP 混合模型并行二表算法程序设计
• 5.1.3 实验结果分析
• 5.2 基于 OpenMP 模型 0-1 背包问题并行二表程序
• 5.2.1 OpenMP 并行编程模型
• 5.2.2 基于 OpenMP 编程模型并行二表算法程序设计
• 5.2.3 实验结果分析
• 5.3 小结
• 结论
• 参考文献
• 致谢
• 附录 A 攻读硕士期间发表论文目录
• 附录 B 攻读硕士期间参加的科研项目