文档介绍：1第四章贪心算法(GreedyAlgorithms)贪心算法基本原理用贪心法求解一些问题,如:哈夫曼编码本章提要:最优装载问题活动安排问题单源最短路径问题最小生成树2一、Greedy算法的基本原理(ElementsofGreedyAlgorithms)Greedy算法的基本思想是求解最优化问题的算法,包含一系列步骤每一步都在一组选择中做当前看最好的选择希望通过做局部优化选择达到全局优化选择Greedy算法不一定总产生优化解Greedy算法是否产生优化解,需要严格证明V0V12V13V21V11V23V22V34672414351213求解最优化问题我们可能会想到用动态规划法,但有时用贪心算法会更简单、有效。例子:背包问题:给定n种物品和一个背包。物品i的重量是wi,其价值为vi,背包的容量为W。应如何选择物品装入背包,使得装入背包中的物品的总价值最大?在选择物品i装入背包时,可以选择物品i的一部分,而不一定要全部装入背包。贪心策略:每次选vi/wi最大的物品i放进包中。背包问题具有最优子结构性质,它可以用动态规划算法来解。但是,用贪心算法更简单,解题效率更高。4贪心算法总是做出在当前看来是最好的选择。也就是说贪心算法并不从整体最优上加以考虑,所以贪心算法不是对所有问题都能得到整体最优解。0-1背包问题:给定n种物品和一个背包。物品i的重量是wi,价值为vi,背包的容量为C。如何选择物品装入背包,使得装入背包中的物品的总价值最大?对每种物品i只有两种选择,要么装入,要么不装入,不能将物品i装入背包多次,也不能只装入物品i的一部分。因此,该问题称为0-1背包问题。对于0-1背包问题,贪心选择之所以不能得到最优解是因为它无法保证最终将背包装满,部分背包空间的闲置使每公斤背包空间所具有的价值降低了。例:背包容量C=10,n=3,三个物品的重量W={3,5,7},三个物品的价值V={9,10,12}。贪心法装入背包的价值为19。但最优值是21。5虽然贪心算法不是对所有问题都能得到整体最优解,但对范围相当广的许多问题能产生整体最优解。如:单源最短路经问题,最小生成树问题,哈夫曼编码问题等。在一些情况下,即使贪心算法不能得到整体最优解,但却是最优解的很好的近似解。如:在下图中求从V0到V3的最短路径问题。V0V12V13V21V11V23V22V34672414351216Greedy算法产生优化解的条件①Optimalsubstructure(最优子结构性质)②Greedy-choiceproperty(贪心选择性质)定义1(最优子结构性质)若一个问题的优化解包括它的子问题的优化解,则称其具有最优子结构性质。定义2(greedy选择性质)若一个优化问题的全局优化解可通过局部优化选择得到,则该问题称为具有greedy选择性质。7证明算法所求解的问题具有优化子结构性质证明算法所求解的问题具有Greedy选择性说明算法确实按照Greedy选择性进行局部优化选择的。Greedy算法正确性证明方法8与动态规划方法的比较动态规划:每一步作一个选择—依赖于子问题的解。贪心方法:每一步作一个选择—不依赖于子问题的解。可用动态规划方法的条件:最优子结构性质;子问题的重叠性质;子问题空间小。可用贪心方法的条件:最优子结构性质;贪心选择性质。动态规划:自底向上求解;贪心方法:自顶向下求解。可用贪心法时,动态规划方法可能不适用;可用动态规划方法时,贪心法可能不适用。9二、活动安排问题(Anactivity-selectionproblem)<1>问题的定义活动安排问题是可以用贪心算法有效求解的一个很好的例子。活动设有n个活动的集合E={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只允许一个活动使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi。如果选择了活动i,则它在半开的时间区间(si,fi]内占用资源。10相容活动若区间[si,fi]与区间[sj,fj]不相交,则称活动i与活动j是相容的。也就是说,当sj≥fi或si≥fj时,活动i与活动j是相容。问题定义活动安排问题是要在所给的活动集合中选出最大的相容活动子集合。sifisjfjtsjfifjsifjsi相容!相容!不相容!