资源描述：
《算法设计与分析6》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、贪心法(GreedyApproach)基本思想算法设计设计要素与动态规划法的比较正确性证明得不到最优解的处理办法应用实例1基本思想实例：最小生成树的Kruskal算法,活动选择问题适用问题：组合优化问题，满足优化原则设计方法：多步判断，解为判断序列选择依据：是否满足约束条件局部优化测度使用贪心法要解决的问题:是否可以得到最优解?不能得到最优解,解与最优解的误差估计2例1活动选择问题S={1,2,…,n}为n项活动的集合s,f分别为活动i的开始和结束时间ii活动i与j相容当且仅当s≥f或s≥fijji求最大的两两相容的活动集思路：按结束时间递增
2、顺序将活动排列为1,2,…,n,使得f≤f≤…≤f12n按照标号从小到大选择3贪心算法算法GdSltGreedySelect1.n←length[S];2.A←{1};3.j←1;4.fori←2ton5.doifdoifs≥fij6.thenA←A∪{i};7.j←i;8.returnA.最后完成时间t=max{f:k∈A}.k4实例输入i1234567891011s130535688212if4567891011121314i解为A={14811}={1,4,8,11}t=145正确性证明定理1算法Select执行到第k步,选择k项活动i
3、=1=1,i,…,i,那么存在最优解A包含12ki=1,i,…,i12k根据定理：算法至多到第n步得到最优解6对步数归纳的证明思路•归纳基础：证明存在最优解包含活动1•归纳步骤：假设按照算法前k步选择都导致最优解，证明第k+1步选择也导致最优解归纳步骤的证明思路1.算法第k步选择活动i=1,i,…,i，根据归12k纳假设，存在最优解A={i=1,i,…,i}∪B12kB是剩下的待选活动集S’的一个最优解2.由归纳基础，存在S’的最优解B’包含ik+13.由
4、B’
5、=
6、B
7、知A’={i=1,i,…,i}∪B’最优12k4.A’={i=1,i,…
8、,i,i}∪(B’−{i})最优.12kk+1k+17证明：归纳基础设S={1,2,…,n}是活动集，活动按截止时间递增顺序排序.k=1,证明存在最优解包含活动1.任取最优解A,A中的活动按照截止时间递增的顺序排列.如果A的第一个活动为j，j≠1,令A’=(A−{j})∪{1},由于f≤f,A’也是最优解，且含有1.1j8证明：归纳步骤假设命题对k为真,证明对k+1也为真.算法执行到第k步,选择了活动i=1,i,…,i,根12k据归纳假设存在最优解A包含i=1,i,…,i,12kA中剩下的活动选自集合S’={i
9、i∈S,s≥f},且ikA={
10、i,i,…,i}∪B12kB是S’的最优解.（若不然,S’的最优解为B*,B*的活动比B多，那么B*∪{1,i,…,i}是S的最2k优解，且比A的活动多,与A的最优性矛盾.）根据归纳基础，存在S’的最优解B’含有S’中的第一个活动，设为i,且
11、B’
12、=
13、B
14、,于是k+1{i,i,...,i}∪B'={i,i,...i,i}∪(B'−{i})12k12kk+1k+1也是原问题的最优解.9贪心算法的设计适用：满足优化原则的组合优化问题问题求解表示成多步判断整个判断序列对应问题的最优解子序列对应子问题的最优解贪心选择：确定一个优化测度——贪心选择依
15、据不考虑以前的选择，只与当前状态有关以优化测度的极大(或极小)作为依据10贪心算法的设计（续）确定是否满足贪心选择性质具有贪心选择性质得到最优解，否则为近似解正确性证明：归纳法：证明贪心法得到最优解对算法步数归纳、对问题规模归纳交换论证：在保证最优性不变的前提下，从一个最优解出发进行逐步替换，最终得到贪心法的解自顶向下计算通过贪心选择，将原问题规约为子问题线性表记录选择的结果11贪心选择性质的证明数学归纳法叙述一个可以归纳证明的命题：•对步数k归纳对于任意k，k步贪心选择得到i,i,…,i,那么12k存在最优解包含i,i,…,i12k•规模k
16、归纳：对于任意k,贪心法得到关于规模为k的问题的最优解归纳基础：k=1,命题为真归纳步骤：假设对17、有1个箱子）•假设对于规模为n−1的输入得到最优解，证明对规模为n的输入也得到最优解14归纳步骤假设对于n−1个集装箱的输入，贪心法都可以得到最优解，考虑n个集装箱
