贪婪算法课程设计.doc

《贪婪算法课程设计.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学与计算机学院课程设计说明书课程名称:算法设计与分析-课程设计课程代码:题目利用贪婪算法实现多种实际问题年级/专业/班:学生姓名:学　　号:开始时间:2010年12月26日完成时间:2011年01月9日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总分（100）指导教师签名：年月日目录一、需求分析-2-1.1问题解决-2-1.2实现思想-2-1.3实现意义-2-二、概要设计-2-2.1算法流程-2-2.2算法证明-5-2.3存储结构-8-2.4核心模块-8-三、详细设计-10-3.1一般贪婪法以及K=2阶贪婪启发法0-1背包源程序

2、-10-3.2贪婪法有限计算机作业调度源程序-16-四、调试分析-18-4.1调试出现问题及分析-18-4.2数据测试与结果-18-4.3时间复杂度-20-4.4算法改进设想-20-五、总结-20-一、需求分析1.1问题解决本次采用贪婪法所解决的问题为：0-1背包问题，异界有限期作业调度问题，分别使得背包中所放物品价值最大，计算机处理作业后所获得利益最大化。在本次贪婪法解决背包问题时，增加了一个K=2阶贪婪启发算法，使得所得解更加接近最优解。1.2实现思想贪婪算法主旨是在解决问题的过程中，采用逐步构建最优的方法，从而达到全局最优的解。在每个阶段都作出一个看上去最优的决策（在一定的标准

3、下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则。而K=2阶贪婪启发算法，即：首先从当前物品中任意选出K=2件物品，然后放入背包，如果这K=2件物品重量大于背包重量C，则放弃，否则，剩余的容量用来考虑将剩余物品按价值密度(pi/wi)递减的顺序装入。通过考虑由启发法产生的解法中最多为k件物品的所有可能的子集来得到最优解。此解将更接近实际的最优解。比如：当前背包承重量C=40，物品重量W={25、20、20}，物品价值P={25，15，15}，一般贪婪法结果为[1，0，0]，背包价值为25，而K=2阶贪婪启发算法解为[0,1,1],背包价值为30。1.3实现意义通过贪婪

4、法解决0-1背包以及有限期作业调度问题，能够检测我们所学知识掌握是否牢固，同时能够快速有效的解决实际问题，而且能够将此算法思想应用于各个领域，解决不同的问题。二、概要设计2.1算法流程A：贪婪法解决0-1背包问题图一B：K=2阶贪婪启发算法解决0-1背包问题图二C：贪婪法解决有限期限计算机作业调度图三2.2算法证明在此证明贪婪启发算法：1、算法描述及实例分析对算法的一个改进是一种启发式搜索算法,称为k阶优化算法。首先将最多k件物品放入背包,如果这k件物品重量大于c,则放弃它。否则,剩余的容量用来考虑将剩余物品按Pi/wi递减的顺序装入。通过考虑由启发法产生的解法中最多为k件物品的所有

5、可能的子集来得到最优解[5]。给出一个实列来解释该算法的运行过程。考虑n=4,w=[2,4,6,7],p=[6,10,12,13],c=11。当k=0时,背包按物品价值密度3,2.5,2,1.86的非递减顺序装入,首先将物品1放入背包,然后是物品2,背包剩下的容量为11-2-4=5个单元,剩下的物品没有一个合适的,因此解为x=[1,1,0,0]。此解获得的价值为16。现在考虑k=1时的贪婪启发法。就是依次验证从取定i对算法的另一个改进思路是一种启发式搜索算法,称为k阶优化算法。首先将最多k件物品放入背包,如果这k件物品重量大于c,则放弃它。否则,剩余的容量用来考虑将剩余物品按pi/w

6、i递减的顺序装入。通过考虑由启发法产生的解法中最多为k件物品的所有可能的子集来得到最优解[5]。我们给出一个实例来解释该算法的运行过程。考虑n=4,w=[2,4,6,7],v=[6,10,12,13],c=11。当k=0时,背包按物品价值密度3,2.5,2,1.86的非递减顺序装入,首先将物品1放入背包,然后是物品2,背包剩下的容量为11-2-4=5个单元,剩下的物品没有一个合适的,因此解为x=[1,1,0,0]。此解获得的价值为16。若k=2,就是依次验证从取定i,j开始的,然后按物品价值密度非递减得到的最优解,同时和k=1时的解进行比较。除了考虑k<2的子集,还必需考虑子集{1,

7、2},{1,3},{1,4},{2,3},{2,4}和{3,4}。首先从最后一个子集开始,它是不可行的,故将其抛弃,剩下的子集经求解分别得到如下结果:[1,1,0,0],[1,0,1,0],[1,0,0,1],[0,1,1,0]和[0,1,0,1],这些结果中最后一个价值为23,它的值比k=0获得的解要高,这个答案即为k=2启发式方法产生的结果。2、近似比的证明当K=0时，即为一般贪婪算法，当K>=1时：令为最优解时，对中的物品价值按从大到小排列，得到、.