并行环境下0-1背包问题的解决策略

论文摘要

本论文主要进行0-1背包问题解决策略的理论研究。论文在对流水线技术和0-1背包问题进行理论研究的基础上,将流水线中的技术融入到待放入背包物品的前期准备工作中,用“贪心算法”思想来求解0-1背包问题。从而对大规模0-1背包问题进行有效求解。0-1背包问题（Knapsack Problem,简称KP）是一个经典的组合优化问题,具有广泛的实际应用背景。生活中的许多问题都可以用背包问题来描述,如资源分配、货仓装载、资金预算、存储分配和项目选择等都可以建模成背包问题,并且它还常常作为其他复杂组合优化问题的一个子问题。但是当背包问题规模过大时,如果想得到最优解是极其困难的,因此开展对大规模0-1背包问题的研究具有重要的意义。传统解决背包问题的方法大体上可以分为两类：精确算法（如动态规划,分支定界,回溯法等）和近似算法（如贪心算法）。因为精确算法的时间复杂性都是呈指数增长的,所以从六十年代逐渐提出了一些近似算法。此外,流水线技术是目前广泛应用于微处理芯片的一项关键技术,他对CPu内部的各条指令的执行方式进行空间并行操作。将流水线技术引进到0-1背包问题的准备阶段,将对背包问题的整体效率产生一定的提高。在阅读了大量中外文献的基础上,本文提出了0-1背包问题的一种新的解决策略。文章介绍了并行机概念,流水线技术,及常见的0-1背包问题解决思路并对他们各自的性能进行了分析。在贪心算法求解思路的启发下,结合0-1背包问题的特性,提出了一个改进的措施,以实现在大规模环境、大数据量的情况下,提高0-1背包问题的搜索速度和解的质量。本论文从最初的数据录入,分析,计算,各个环节入手,从整体上把握性能提高的各个环节。

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 选题背景和意义
• 1.2 本论文研究内容和主要工作
• 1.3 本论文的组织和结构
• 第二章 并行计算
• 2.1 并行计算简介
• 2.1.1 并行计算的定义
• 2.1.2 并行计算的研究内容
• 2.2 并行算法分类
• 2.3 并行算法技术
• 2.3.1 多核并行算法的分类
• 2.3.2 单核与多核平台上的多线程技术区别
• 第三章 流水线技术
• 3.1 流水线简介
• 3.1.1 流水线产生背景
• 3.1.2 流水线术语
• 3.2 流水线工作原理
• 3.2.1 流水线分类
• 3.2.2 流水线特点
• 3.3 流水线性能指标
• 3.3.1 流水线吞吐率
• 3.3.2 流水线加速比
• 3.3.3 流水线效率
• 3.3.4 流水线最佳段数
• 3.4 流水线相关
• 3.4.1 结构相关
• 3.4.2 数据相关
• 3.4.3 控制相关
• 第四章 组合优化中0-1背包问题
• 4.1 动态规划法
• 4.1.1 动态规划法的基本思想
• 4.1.2 动态规划法的求解基本步骤
• 4.1.3 动态规划法的算法描述及设计
• 4.2 回溯法
• 4.2.1 回溯法的基本思想
• 4.2.2 回溯法的求解基本步骤
• 4.2.3 回溯法的算法描述及分析
• 4.3 分支限界法
• 4.3.1 分支限界法的基本思想
• 4.3.2 分支限界法的求解基本步骤
• 4.3.3 分支限界法的算法描述及设计
• 第五章 流水线技术的引入
• 5.1 先行控制技术的工作模式
• 5.2 执行方式
• 5.3 为背包问题做的准备工作
• 第六章 “贪心算法”解决0-1背包问题
• 6.1 贪心算法
• 6.1.1 贪心算法的基本思想
• 6.1.2 贪心算法的求解步骤
• 6.1.3 贪心算法求解背包问题的描述
• 6.1.4 贪心算法对结合实例0-1背包问题分析
• 6.2 贪心算法在0-1背包问题中的应用
• 6.2.1 基本思想
• 6.2.2 算法描述及对应的流程图
• 6.2.3 实例分析
• 6.2.4 性能分析
• 第七章 总结与展望
• 参考文献
• 攻读硕士学位期间发表的论文及参与的项目
• 致谢