计算机算法设计与分析--第4章 贪心算法.ppt

计算机算法设计与分析 Design and Analysis puter Algorithms
第四章贪心算法
Greedy Algorithm
*
1
提纲
一、贪心算法的基本思想
二、活动安排问题
三、最优装载
四、哈夫曼编码
五、单源最短路径
六、最小生成树
七、多机调度问题
Date
2
提纲
一、贪心算法的基本思想
二、活动安排问题
三、最优装载
四、哈夫曼编码
五、单源最短路径
六、最小生成树
七、多机调度问题
Date
3
贪心算法总体思想
贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。贪心法在解决问题的策略上目光短浅,只根据当前已有的信息就做出选择,而且一旦做出了选择,不管将来有什么结果,这个选择都不会改变。
这种局部最优选择并不总能获得整体最优解(Optimal Solution),但通常能获得近似最优解(Near-Optimal Solution)。
Date
4
贪心算法总体思想
例:用贪心法求解付款问题。
假设有面值为5元、2元、1元、5角、2角、1角的货币,需要找给顾客4元6角现金,为使付出的货币的数量最少,首先选出1张面值不超过4元6角的最大面值的货币,即2元,再选出1张面值不超过2元6角的最大面值的货币,即2元,再选出1张面值不超过6角的最大面值的货币,即5角,再选出1张面值不超过1角的最大面值的货币,即1角,总共付出4张货币。
Date
5
假设有面值为1分、5分、1角1分的货币,需要找给顾客1角5分现金,
仍按贪心算法如何?
Date
6
贪心算法的基本要素
贪心选择性质
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。
对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所作的贪心选择最终导致问题的整体最优解。
最优子结构性质
当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。
Date
7
贪心算法正确性证明方法
证明算法所求解的问题具有贪心选择性;
证明算法所求解的问题具有最优子结构;
证明算法确实按照贪心选择性进行局部优化选择。
Date
8
动态规划与贪心算法的比较
相同点:
都具有最优子结构性质。
不同点:
贪心算法具有贪心选择性质;
动态规划算法具有子问题重叠性,子问题空间小;
动态规划算法通常以自底向上的方式解各子问题;
贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。
可用贪心算法时,动态规划方法可能不适用;
可用动态规划方法时,贪心算法可能不适用。
Date
9
0-1背包问题和背包问题
0-1背包问题:
给定n种物品和一个背包。物品i的重量是Wi,价值为Vi,背包容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大?
在选择装入背包的物品时,对每种物品i只有2种选择,即装入或不装入。
背包问题:
与0-1背包问题类似,所不同的是在选择物品i装入背包时,可以选择物品i的一部分,而不一定要全部装入背包,1≤i≤n。
Date
10