21、贪婪算法课程设计

数学与计算机学院课程设计说明书课程名称:算法设计与分析-课程设计课程代码:8404101题目利用贪婪算法实现多种实际问题年级/专业/班:学生姓名:学号:开始时间: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-三、详细设计...................................................................................................................-11-3.1一般贪婪法以及K=2阶贪婪启发法0-1背包源程序......................................-11-3.2贪婪法有限计算机作业调度源程序...................................................................-16-四、调试分析...................................................................................................................-18-4.1调试出现问题及分析............................................................................................-18-4.2数据测试与结果....................................................................................................-18-4.3时间复杂度............................................................................................................-20-4.4算法改进设想........................................................................................................-20-五、总结...........................................................................................................................-20-贪婪算法解决多种实际问题-2-一、需求分析1.1问题解决本次采用贪婪法所解决的问题为：0-1背包问题，异界有限期作业调度问题，分别使得背包中所放物品价值最大，计算机处理作业后所获得利益最大化。在本次贪婪法解决背包问题时，增加了一个K=2阶贪婪启发算法，使得所得解更加接近最优解。1.2实现思想贪婪算法主旨是在解决问题的过程中，采用逐步构建最优的方法，从而达到全局最优的解。在每个阶段都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则。而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实现意义通过贪婪法解决0-1背包以及有限期作业调度问题，能够检测我们所学知识掌握是否牢固，同时能够快速有效的解决实际问题，而且能够将此算法思想应用于各个领域，解决不同的问题。二、概要设计2.1算法流程A：贪婪法解决0-1背包问题贪婪算法解决多种实际问题-3-开始WI/Pi是否是当前最大值i++输入物品重量以及价值计算Wi/PiNYWi是否小于C（背包当前承重量）n++Y放入背包，赋值Wi=无穷大N&&nNnN结束n=Nn=N图一B：K=2阶贪婪启发算法解决0-1背包问题贪婪算法解决多种实际问题-4-开始输入物品重量及对应价值计算Value=(Wi+Wj)+(Pi+Pj)Value是否为当前最大Wi+Wj是否小于背包称重量CY将对应物品放入背包YN放弃此两个物品N没有任何i、j满足条件N执行一般贪婪算法图二C：贪婪法解决有限期限计算机作业调度贪婪算法解决多种实际问题-5-开始输入作业时间T、期限D以及对应效益P计算效益比（Pi\Ti）是否是当前最大N完成时是否超期DY忽略此作业Y调入计算机执行N结束N是否还有满足要求的作业Y图三2.2算法证明在此证明贪婪启发算法：1、算法描述及实例分析对算法的一个改进是一种启发式搜索算法,称为k阶优化算法。首先将最多k件物品放入背包,如果这k件物品重量大于c,则放弃它。否则,剩余的容量用来考虑将剩余物品贪婪算法解决多种实际问题-6-按Pi/wi递减的顺序装入。通过考虑由启发法产生的解法中最多为k件物品的所有可能的子集来得到最优解[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/wi递减的顺序装入。通过考虑由启发法产生的解法中最多为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时的解进行比较。除了考虑k2的子集,还必需考虑子集{1,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时：令opP为最优解时，对opP中的物品价值按从大到小排列，得到^1P、^2P...^KP...^lP，其中^1P到^kP必定出现在某个K阶全排列中。令maxP为该全排列所对应的用K阶优化法求得解1P、2P、3P,....nP.现考虑maxP中扣除1P到kP得部分，即1kP到lP按照（价值\重量）的递减顺序进行排列，得到1'kP...nP'记为LP'。所有物品集中扣除maxP的剩余物品也按（价值\重量）的递减顺序进行排列。记为1*kP...jP*记为LP*。再对opP中扣除1P到kP得部分按照（价值\重量）的递减顺序进行排列，得到'^1kP...'^lP，记为LP'^。（1）证明maxP+'mP=opP贪婪算法解决多种实际问题-7-考虑将1*kP...jP*中的物品顺序装入maxP中kP之后的位置，设第一个无法装入的为*mP，现在从*mP，...,nP*中顺序查找第一个无法放入maxP中且出现在lP'的成员，记为'mP。这样的'mP一定存在，因为若不存在，则说明^'LP中的物品全部在'LP中，此时maxP=opP，为最优解。显然若将'mP再加入maxP中，则超过背包负重。也就是说（'LP+'mP）的重量大于LP'^的重量。由LP'定义可知LP'的价值密度大于^'LP的价值密度，又由于'mP是^'LP的成员，所以有集合（'LP+'mP）的价值密度大于LP'^的价值密度。价值密度X重量=价值，故（'LP+'mP）的价值大于LP'^的价值，即（'LP+'mP）=LP'^将该不等式左右各加上排列（1P...kP）的值，得到maxP+'mP=opP（2）证明'mPopP/(K+1)因为'mPkP^...^1P所以opP1^P+...+^KP+'mP(K+1