算法分析与设计[4].ppt

《算法分析与设计[4].ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章贪心方法什么是贪心方法背包问题单源点最短路径最优归并模式活动安排问题实例:找硬币假设有三种硬币,面值分别为5分,2分和1分,给顾客找零钱时希望拿出的硬币个数最少找零1角2分:2个5分,1个2分2个5分,2个1分6个2分找零算法:先找出一个面值不超过1角2分的最大硬币(5分)从1角2分中减去5分,剩7分再找出一个面值不超过7分的最大硬币(5分)从7分中减去5分,剩2分最后找出一个面值不超过2分的最大硬币(2分)贪心算法的思想:贪心算法总是作出在当前看来最好的选择。贪心算法并不从整体最优考虑,因

2、此它所作出的选择是在某种意义上的局部最优选择贪心算法通常包含一个用以寻找局部最优解的迭代过程对于某些实例,这些局部最优解转变为全局最优解而对于另外一些实例,贪心算法不能找到全局最优解贪心算法求解问题的速度比较快,因为算法的每一步都是在少量信息的基础上考虑局部最优解,这样使得每一步的计算量比较小,所以算法效率比较高4.1什么是贪心方法A(1)A(2)…A(n-1)A(n)某一问题的n个输入B1(1)B1(2)…B1(m)该问题的一种解（可行解）是A的一个子集满足一定的条件约束条件Bk(1)Bk(2)

3、…Bk(m)…目标函数取极值最优解4.1什么是贪心方法根据题意，选取一种量度标准，然后按量度标准对n个输入排序，按顺序一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中，这种能够得到某种量度意义下的最优解的分级处理方法就是贪心方法。量度标准A(1)A(2)…A(n)A’(1)A’(2)…A’(n)S(1)S(2)…量度标准意义下的部分最优解原问题的n个输入排序后的n个输入A’(j)贪心方法的抽象化控制int*GREEDY(in

4、t*A,intn){solution=Ф;for(i=1;i<=n;i++){x=SELECT(A)if(FEASIBLE(solution,x)==1)solution=UNION(solution,x);}return(solution);}按某种最优量度标准从集合A中选择一个输入赋给x，并从A中除去判断x是否可以包含在解向量中将x与解集合合并并修改目标函数4.1背包问题的贪心算法问题描述已知有n种物品和一个可容纳M重量的背包，每种物品i的重量为wi，假定将物品i的某一部分xi放入背包就会得到

5、pixi的效益(0≤xi≤1,pi>0)，采用怎样的装包方法才会使装入背包物品的总效益为最大呢？问题的形式描述极大化∑pixi约束条件∑wixi≤M0≤xi≤1,pi>0,wi>0,1≤i≤n1≤i≤n1≤i≤n目标函数背包问题实例(x1,x2,x3)∑wixi∑vixi①(1,2/15,0)2028.2②(1,0,1/5)2028③(0,2/3,1)2031④(0,1,1/2)2031.5其中的4个可行解：有3个物品,即n=3,背包能容纳的最大重量为20,即c=20物品的价值和重量:(v1,v2

6、,v3)=(25,24,15),(w1,w2,w3)=(18,15,10)最优解贪心算法求解背包问题确定贪心选择策略①选择价值高的物品放入背包将物品按价值的降序排列:(v1,v2,v3)=(25,24,15)按该次序将物品一件件放到背包中,先装物品1,即x1=1,w1=18,v1x1=25;再装物品2,因约束条件为∑wixi≤c=20,所以物品2只能装入重量为2的一小部分,即x2=2/15;最后得到总价值为∑vixi=25+24*2/15=28.2实例：n=3,c=20(v1,v2,v3)=(25

7、,24,15)(w1,w2,w3)=(18,15,10)这是一个次优解，原因是背包容量消耗的过快确定贪心选择策略②选择重量轻的物品放入背包将物品按重量的升序排列:(w3,w2,w1)=(10,15,18)按该次序将物品放到背包中,让容量尽可能慢的被消耗先装物品3,即x3=1,w3=10,v3x3=15;再装入物品2,因约束条件为∑wixi≤c=20,所以物品2只能装入重量为10的一部分,即x2=10/15=2/3;最后得到总价值为∑vixi=15+24*2/3=31这仍是一个次优解,原因是容量在慢

8、慢消耗的过程中,效益值却没有迅速的增加实例：n=3,c=20(v1,v2,v3)=(25,24,15)(w1,w2,w3)=(18,15,10)③选择单位重量价值高的物品放入背包将物品按vi/wi比值的降序排列:(v2/w2,v3/w3,v1/w1)=(24/15,15/10,25/18)即每一次装入的物品使它占用的单位重量获得当前最大的单位价值先装入物品2,即x2=1,w2=15,v2x2=24;再装入物品3,因约束条件为∑wixi≤c=20,所以物品3只能装入重量为5的一部分,