算法课件第4章贪心算法

《算法课件第4章贪心算法》由会员分享，可在线阅读，更多相关《算法课件第4章贪心算法（72页珍藏版）》请在金锄头文库上搜索。

1、1,第4章 贪心算法,马志强,http:/ Deadly Sins,2,Lust,Gluttony,Greed,Sloth,Wrath,Envy,Pride,3,急功近利?,向着某一天终于要达到的那个终极目标迈步还不够，还要把每一步骤看作目标，使它作为步骤而起作用。 歌德,4,理解贪心算法的概念 掌握贪心算法的基本要素 （1）最优子结构性质 （2）贪心选择性质 理解贪心算法与动态规划算法的差异 理解贪心算法的一般理论,学习要点,5,通过应用范例学习贪心设计策略 （1）活动安排问题； （2）最优装载问题； （3）哈夫曼编码； （4）单源最短路径； （5）最小生成树； 贪心设计策略 （1）解决优化

2、问题 （2）策略：逐步解决问题。总是作出当前看起来最好的选择，即局部最优解,学习要点,6,贪心算法的基本概念,例1 给定4种硬币（五角、一角、五分、一分） 用最少的硬币找顾客n角n分（六角三分） 贪心算法 当前看起来最优的选择（局部最优解）：每次选不超过余额的面值最大的硬币 1个五毛剩余一毛三 1个一毛剩余三分 3个一分,得到的结果是一个整体最优解,7,贪心算法的基本概念,例2 给定3种硬币（一角一、五分、一分） 用最少的硬币找顾客n毛n分（一角五） 贪心算法 1个一角一 4个一分 最优解 3个五分,不是整体最优解,8,贪心算法的基本概念,贪心算法何时可以得到（整体）最优解？ 优化问题需具有

3、（1）贪心选择性 （2）优化子结构,9,定义（活动） 设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，而在同一时间内只有一个活动能使用这一资源。 每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si fi 。如果选择了活动i，则它在半开时间区间si, fi)内占用资源。,活动安排问题,定义（相容活动） 若区间si, fi)与区间sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当sifj或sjfi时，活动i与活动j相容。,或者,10,活动安排问题,11,活动安排问题,贪心算法 假设各个活动按活动结束时间 fi 排序 f1 f2 fn 选择活动 1

4、 (结束时间最早的活动) 从2开始按顺序考察各个活动，选择第一个与活动 1 相容的活动 i 从i+1开始按顺序考察各个活动，选择第一个与活动 i 相容的活动 j 。,每次选择与现有活动相容的结束时间最早的活动,12,活动安排问题,贪心算法 void GreedySelector(int n, Type s, Type f, bool A) A1=true; int j=1; for (int i=2;i=fj) Ai=true; j=i; else Ai=false; ,13,活动安排问题,14,由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完

5、成时间的相容活动加入集合A中。 按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。,活动安排问题,如果输入的活动已按结束时间非减序排列，算法只需(n)的时间安排n个活动 如果输入的活动未按结束时间非减序排列，算法需要(nlogn)的时间重排。,贪心算法并不总能求得问题的整体最优解。 但对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。 这个结论可以用数学方法严格证明。,15,活动安排问题,证明贪心算法可以得到最优解（归纳法） 证明第

6、一次选择活动1是正确的 即活动1在最优解中 证明选择完活动1后，问题变成了输入为 E=与活动1相容的活动 的子问题 因为第二个选择的活动 i 是 E 中结束时间最早的，所以活动 i 是正确的 依次类推所有的选择都是正确的,16,活动安排问题,证明活动1在最优解中 假设 是活动安排问题的一个最优解， A中结束时间最早的活动为k 如果k=1，活动1在最优解中 如果k1， 也是一个最优解,贪心选择性,17,活动安排问题,证明选择完活动1后，问题变成了输入为 E=与活动1相容的活动 的子问题 假设 是活动安排问题的一个最优解，且包含活动1 于是A=A-1是针对E的活动安排问题的最优解 否则，假设E中有

7、更优解B B+1是针对E的一个更优解,优化子结构,18,活动安排问题获得最优解得基本条件,贪心选择性 （第一次）作出贪心选择是正确的 优化子结构 （第一次）做完贪心选择后，得到一个与原问题定义相同（输入不同）的子问题,19,最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。,贪心算法的基本要素,贪心选择性质 (1) 贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 (2) 贪心算法则

8、通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。动态规划算法通常以自底向上的方式解各子问题。,20,问题的定义 优化解的结构分析 算法设计 算法复杂性 算法正确性证明,贪心算法的求解过程,21,最优装载问题,输入 n个集装箱：集装箱i的重量为wi 轮船的载重量C 输出 （尽可能多）装入轮船的集装箱 形式化 s.t.,22,最优装载问题,贪心算法 逐个选择集装箱装入轮船 每次选择最轻的集装箱,void Loading(int x, Type w, Type C, int n) int *t = new int n+1; Sort(w,

9、 t, n); for (int i = 1; i = n; i+) xi = 0; for (int i = 1; i = n ,时间复杂性：O(n logn),23,最优装载问题,设集装箱已经依其重量从小到大排 贪心选择性 第一步选择第一个（最轻的）集装箱是正确的，即第一个集装箱一定在最优解中 设最优解选择的集装箱为a, b, c, （按重量从小到大排列） 如果a=1, 则最轻的集装箱在最优解中 如果a1，1, b, c, 同样为问题的最优解,24,最优装载问题,设集装箱已经依其重量从小到大排 优化子结构 设问题的最优解为1, b, c, , （按重量从小到大排列） 则b, c, , 针对

10、以下输入的最优装载问题的最优解 集装箱2, , n 轮船载重C-w1,25,最优装载问题,结论 贪心算法可以获得最优装载问题的最优解,26,哈夫曼编码,对字符编码 10,000个字符：对每个字符用0,1编码 定长编码 编码长度：10,000 * 3=30,000,27,哈夫曼编码,对字符编码 10,000个字符：对每个字符用0,1编码 变长编码 编码长度： 4500*1+1300*3+1200*3+1600*3+900*4+500*4= 22400,28,哈夫曼编码,前缀码 对字符的0,1编码 任意字符的编码都不是其它字符编码的前缀 接收：001011101 解码：aabe,29,哈夫曼编码,

11、前缀码二叉树 左分支：0 右分支：1 树叶代表字符 从树根到树叶的路径代表字符编码 所有顶点的度非0即2,30,哈夫曼编码,平均码长（二叉树代价） 一颗根据字符集C构造的二叉树T 对于C中的任意字符x 其出现频率（权重）为 f (x) 其在T中的深度为 dT (x) 则T 的平均码长（代价为）,B(T)=45*1+12*3+13*3+16*3+5*4+9*4=224,31,哈夫曼编码,输入 字符集C，对于C中的任意字符x，其出现频率（权重）为 f (x) 输出 平均码长最短的前缀码编码方案（哈夫曼编码） 即代价最小的前缀二叉树,32,哈夫曼编码,贪心算法 选择权重最小的两棵子树构成二叉树 新的

12、二叉树的权重等于两棵子树权重之和,33,哈夫曼编码,初始：,第1步：,第2步：,34,哈夫曼编码,初始：,第2步：,第3步：,35,哈夫曼编码,初始：,第3步：,第4步：,36,哈夫曼编码,初始：,第4步：,第5步：,37,哈夫曼编码,Huffman(C，F) (使用堆操作实现) n|C|； QC; /* 用BUILD-HEAP 建立堆 */ FOR i1 To n-1 zAllocate-Node( ); xleftzExtract-MIN(Q); /* 堆操作*/ yrightzExtract-MIN(Q); /* 堆操作*/ f(z)f(x)+f(y); insert(Q,z); /*

13、堆操作*/ Return Extract-MIN(Q).,初始化优先队列需要(n)计算时间 最小堆的DeleteMin和Insert运算均需(logn)时间 n1次的合并总共需要(nlogn)计算时间。 哈夫曼算法的计算时间为(nlogn) 。,38,哈夫曼算法的正确性 证明哈夫曼算法的正确性，只要证明最优前缀码问题具有如下两个性质： (1)贪心选择性质 (2)最优子结构性质。,哈夫曼编码,39,贪心选择性 设C 是字母表，“cC，c 具有频率f(c), x、y 是C 中具有最少频率的两个字符，则存在一个C 的优化前缀树，x 与y 的编码具有相同长度，且仅在最末一位不同。,哈夫曼编码,证：,设

14、T 是一个C 的优化前缀树，且b 和c 是具有最大深度的两个字符 不失一般性，设f(b)f(c),f(x)f(y).,因x 与y 是具有最低频率的字符, f(b)f(x),f(c)f(y)。,从T 构造T，交换T 的b 和x；,从T构造T，交换T 的y 和c；,往证T是最大前缀树.,40,哈夫曼编码,证: B(T)-B(T)= cCf(c)dT(c)-cCf(c)dT(c),f(b)f(x),dT(b)dT(x) (因为b 的深度最大) B(T)-B(T)0, B(T)B(T),同理可证B(T)B(T). 于是B(T)B(T).,由于T 是最优化的，所以B(T)B(T). 于是,B(T)=B(

15、T)，所以T是C 的最优化前缀编码树.,在T中, x 和y 具有相同长度编码, 而且仅最后一位不同。,= f(x)dT(x)+f(b)dT(b)-f(x)dT(x)- f(b)dT(b),= f(x)dT(x)+f(b)dT(b)-f(x)dT(b)- f(b)dT(x),= (f(b)-f(x)(dT(b)-dT(x),41,优化子结构 设T 是字母表C 的优化前缀树，“cC，f(c)是c 在文件中出现的频率。设x、y 是T 中任意两个相邻叶结点，z 是它们的父结点，则z 作为频率为f(z)=f(x)+f(y)的字符，T=T-x,y表示了字母表C=C-x,yz的优化前缀编码树。,哈夫曼编码,证: B(T)=B(T)+f(x)+f(y),vC-x,y, dT(v)=dT(v)。于是f(v)dT(v)=f(v)dT(v)。,由于dT(x)=dT(y)=dT(z)+1， f(x)dT(x)+f(y)dT(y)=(f(x)+f(y)(dT(z)+1)=(f(x)+f(y)dT(z)+(f(x)+f(y),由于f(x)+f(y)=f(z), f(x)dT(x)+f(y)dT(y)=f(z)dT(z)+(f(x)+f(y).,于是 B(T)=B(T)+f(x