文档介绍：第三章贪心方法
一般方法
1. 问题的一般特征
问题有n个输入,问题的解是由这n个输入的某个子集组成,这个子集必须满足某些事先给定的条件。
约束条件:子集必须满足的条件;
可行解:满足约束条件的子集;可行解可能不唯一;
目标函数:用来衡量可行解优劣的标准,一般以函数的形式给出;
最优解:能够使目标函数取极值(极大或极小)的可行解。
分类:根据描述问题约束条件和目标函数的数学模型的特性和问题的求解方法的不同,可分为:线性规划、整数规划、非线性规划、动态规划等。
——最优化问题求解
贪心方法:一种改进的分级的处理方法,可对满足上述特征的某些问题方便地求解。
2. 贪心方法的一般策略
问题的一般特征:问题的解是由n个输入的、满足某些事先给定的条件的子集组成。
1)一般方法
根据题意,选取一种度量标准。然后按照这种度量标准对n个输入排序,并按序一次输入一个量。
如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解,则不把此输入加到这部分解中。否则,将当前输入合并到部分解中从而得到包含当前输入的新的部分解。
这一处理过程一直持续到n个输入都被考虑完毕,则记入最优解集合中的输入子集构成这种量度意义下的问题的最优解
贪心方法: 这种能够得到某种量度意义下的最优解的分级处理方法
称为贪心方法
注:
贪心解最优解
直接将目标函数作为量度标准也不一定能够得到问题的最优解
使用贪心策略求解的关键是选取能够得到问题最优解的量度标准。
3. 贪心方法的抽象化控制描述
procedure GREEDY(A,n)
//A(1:n)包含n个输入//
solution←Φ//将解向量solution初始化为空//
for i←1 to n do
x←SELECT(A) //按照度量标准,从A中选择一个输入,
其值赋予x并将之从A中删除//
if FEASIBLE(solution,x) then //判定x是否可以包含在当前解向量
中,即是否能共同构成可行解//
solution←UNION(solution,x) //将x和当前的解向量合并成
新的解向量,并修改目标函数//
endif
repeat
return
end GREEDY
背包问题
已知n种物品具有重量(w1,w2,…,wn)和效益值(p1,p2,…,pn) ,及一个可容纳M重量的背包;设当物品i全部或一部分xi放入背包将得到pi xi的效益,这里,0≤ xi ≤1, pi >0。
问题:采用怎样的装包方法才能使装入背包的物品的总效益最大?
分析:
①装入背包的总重量不能超过M
②如果所有物品的总重量不超过M,即≤M,则把所有的物品都装入背包中将获得最大可能的效益值
③如果物品的总重量超过了M,则将有物品不能(部分/全部)装入背包中。由于0≤xi≤1,所以可以把物品的一部分装入背包,故最终背包中可刚好装入重量为M的若干物品(整体或一部分)。这种情况下,如果背包没有被装满,则显然不能获得最大的效益值。
目标:使装入背包的物品的总效益达到最大。
问题的形式描述
目标函数:
约束条件:
可行解:满足上述约束条件的任一(x1,x2,…,xn) 都是问题
的一个可行解——可行解可能为多个。
(x1,x2,…,xn)称为问题的一个解向量
最优解:能够使目标函数取最大值的可行解是问题的最优解
——最优解也可能为多个。
背包问题的实例
设,n=3,M=20,
(p1,p2,p3) = (25,24,15), (w1,w2,w3) = (18,15,10)。
可能的可行解如下:
(x1,x2,x3)
①(1/2,1/3,1/4) //没有装满背包//
②(1, 2/15, 0 ) 20
③(0, 2/3, 1) 20 31
④(0, 1, 1/2) 20
2. 贪心策略求解
度量标准的选择:三种不同的选择
1)以目标函数作为度量
即,每装入一件物品,就使背包获得最大可能的效益增量。
该度量标准下的处理规则是:
●按效益值的非增次序将物品一件件地放入到背包;
●如果正在考虑的物品放不进去,则只取其一部分装满背包:如果该物品的一部分不满足获得最大效益增量的度量标准,则在剩下的物品种选择可以获得最大效益增量的其它物品,将它或其一部分装入背包。
如:若ΔM=2,背包外还剩两件物品i,j,且有(pi= 4,wi=4) 和(pj= 3,wj=2),则下一步应选择j而非i放入背包:
pi/2 = 2 < pj= 3
实例分析()
∵ p1>p