算法设计与分析04贪心算法.ppt

第六章贪心算法主要内容:引言最优化问题（optimizationproblems）是指这样一类问题，问题给定某些约束条件（constraint），满足这些约束条件的问题解称为可行解（feasiblesolution）。通常满足约束条件的解不是惟一的。为了衡量可行解的好坏，问题还给出了某个数值函数，称为目标函数（objectivefunction），使目标函数取最大（或最小）值的可行解称为最优解（optimalsolution）。贪心法是通过分步决策（stepwisedecision）的方法来求解问题的。
贪心法每一步上用作决策依据的选择准则被称为最优量度标准（optimizationcriterion）。
在根据最优量度标准选择分量的过程中，还需要使用一个可行解判定函数。
贪心策略并不是从整体上加以考虑的，它所做出的选择只是当前看似最佳选择，必须进一步证明该算法最终导致问题的一个整体最优解。Greedy算法的基本思想
求解最优化问题的算法包含一系列步骤
每一步都有一组选择
作出在当前看来最好的选择
希望通过作出局部优化选择达到全局优化选择
Greedy算法不一定总产生优化解
Greedy算法是否产生优化解，需严格证明
Greedy算法产生优化解的条件
Greedy-choice-property
OptimalsubstructureGreedy选择性若一个优化问题的优化解包含它的
子问题的优化解，则称其具有优化
子结构与动态规划方法的比较证明算法所求解的问题具有优化子结构
证明算法所求解的问题具有Greedy选择性
证明算法确实按照Greedy选择性进行局部优化选择【程序6－1】贪心法
SolutionTypeGreedy(STypea[],intn)
{
SolutionTypesolution=;
for(inti=0;i<n;i++){
STypex=Select(a);
if(Feasiable(solution,x))
solution=Union(solution,x);
}
returnsolution;
}6.2背包问题6.2.1问题描述6.2.2贪心法求解背包问题的最优解必须使下列目标函数取最大值：例6－1
设有载重能力M=20的背包，3件物品的重量为:（w0,w1,w2）=(18,15,10)，物品装入背包的收益为：（p0,p1,p2）=(25,24,15)。2.贪心策略求解
度量标准的选择：三种不同的选择
1）以目标函数作为度量
即，每装入一件物品，就使背包获得最大可能的效益增量。
该度量标准下的处理规则是：
●按效益值的非增次序将物品一件件地放入到背包；
●如果正在考虑的物品放不进去，则只取其一部分装满背包：如果该物品的一部分不满足获得最大效益增量的度量标准，则在剩下的物品种选择可以获得最大效益增量的其它物品，将它或其一部分装入背包。
如：若ΔM=2,背包外还剩两件物品i,j，且有(pi＝4，wi＝4)和(pj＝3，wj＝2)，则下一步应选择j而非i放入背包：
pi/2=2＜pj＝3实例分析（例3.1)
∵p1＞p2＞p3
∴首先将物品1放入背包，此时x1＝1，背包获得p1＝25的效益增量，同时背包容量减少w1＝18个单位，剩余空间ΔM=2。
其次考虑物品2和3。就ΔM=2而言有，只能选择物品2或3的一部分装入背包。
物品2：若x2＝2/15，则p2x2＝16/5＝3.1
物品3：若x3＝2/10，则p3x3＝3
为使背包的效益有最大的增量，应选择物品2的2/15装包，即
x2＝2/15
最后，背包装满，ΔM=0，物品3不装包，即x3＝0。
背包最终可以获得效益值＝x1p1＋x2p2＋x3p3
＝28.2(次优解,非问题的最优解)2）以容量作为度量标准
以目标函数作为度量标准所存在的问题：尽管背包的效益值每次得到了最大的增加，但背包容量也过快地被消耗掉了，从而不能装入“更多”的物品。
改进：让背包容量尽可能慢地消耗，从而可以尽量装入“较多”的物品。
即，新的标准是：以容量作为度量
该度量标准下的处理规则：
●按物品重量的非降次序将物品装入到背包；
●如果正在考虑的物品放不进去，则只取其一部分装满背包；
实例分析（例3.1)
∵w3＜w2＜w1
∴首先将物品3放入背包，此时x3＝1，背包容量减少w3＝10个单位，还剩余空间ΔM=10。同时，背包获得p3＝15的效益增量。
其次考虑物品2。就ΔM=10而言有，也只能选择物品2的一部分装入背包。下一步将放入物品2的10/15装包，即
x2＝10/15＝2/3
最后，背包装满ΔM=0，物品1将不能装入背包，故x1＝0。
背包最终可以获得效益值＝x1p1＋x2p2＋x3p3
＝31(次优解,非问题的最优解)
存在的问题：效益值没有得到“最大程度