第五章GreedyAlgorithm--精品PPT课件.ppt
《第五章GreedyAlgorithm--精品PPT课件.ppt》由会员分享,可在线阅读,更多相关《第五章GreedyAlgorithm--精品PPT课件.ppt(52页珍藏版)》请在三一文库上搜索。
1、第五章 Greedy Algorithm,邹权(博士) 计算机科学系,5.1 Elements of Greedy Algorithms 5.2 An activity-selection problem 5.3 Huffman codes 5.4 Minimal spanning tree problem,提要,5.1 Elements of Greedy Algorithms,Greedy算法的基本概念 Greedy选择性 优化子结构 与动态规划方法的比较 Greedy算法正确性证明方法,4,Optimal,Local Optimal,Greedy算法的基本思想 求解最优化问题的算法包含一
2、系列步骤 每一步都有一组选择 作出在当前看来最好的选择 希望通过作出局部优化选择达到全局优化选择 Greedy算法不一定总产生优化解 Greedy算法是否产生优化解,需严格证明 Greedy算法产生优化解的条件 Greedy-choice-property Optimal substructure,Greedy算法的基本概念,Greedy选择性,Greedy选择性 若一个优化问题的全局优化解可以通过 局部优化选择得到,则该问题称为具有 Greedy选择性. 一个问题是否具有Greedy选择性需证明,若一个优化问题的优化解包含它的 子问题的优化解,则称其具有优化 子结构,优化子结构,与动态规划方
3、法的比较,动态规划方法可用的条件 优化子结构 子问题重叠性 子问题空间小 Greedy方法可用的条件 优化子结构 Greedy选择性 可用Greedy方法时,动态规划方法可能不适用 可用动态规划方法时,Greedy方法可能不适用,证明算法所求解的问题具有优化子结构 证明算法所求解的问题具有Greedy选择性 证明算法确实按照Greedy选择性进行局部优化选择,Greedy算法正确性证明方法,5.2 An activity-selection problem,问题的定义 优化解的结构分析 算法设计 算法复杂性 算法正确性证明,问题的定义,活动 设S=1,2,n是n个活动的集合,各个活动使 用同一
4、个资源,资源在同一时间只能为一个活动使用 每个活动i有起始时间si,终止时间fi,si fi 相容活动 活动i和j是相容的,若sjfi或sifj,即,Sj,fj,Si,fi,问题定义 输入:S=1, 2, , n,F= si,fi ,ni1 输出:S的最大相容集合,贪心思想: 为了选择最多的相容活动,每次选fi最小的活动,使我们能够选更多的活动,引理1 设S=1,2,n是n个活动集合,si,fi 是活动 的起始终止时间,且f1f2.fn,S的活动选 择问题的某个优化解包括活动1. 证 设A是一个优化解,按结束时间排序A中活动, 设其第一个活动为k,第二个活动为j. 如果k=1,引理成立. 如果
5、k1,令B=A-k1, 由于A中活动相容,f1fk sj , B中活动相容. 因为B=A, 所以B是一个优化解,且包括活动1.,优化解结构分析,引理2.设S=1, 2, , n是n个活动集合,si,fi是活动i 的起始终止时间,且f1f2.fn,设A是S的调 度问题的一个优化解且包括活动1,则A=A-1 是S=iS|sif1的调度问题的优化解. 证.显然,A中的活动是相容的. 我们仅需要证明A是最大的. 设不然,存在一个S 的活动选择问题的优化解 B,BA. 令B=1B. 对于iS, si f1, B中活动相容. B是S的一个解. 由于|A|=|A|+1, B=B+1A+1=A,与A最 大矛盾
6、.,引理2说明活动选择问题具有优化子结构,Greedy选择性 引理3.设 S=1, 2, ., n 是 n 个活动集合,f0=0, li 是 Si = jS | sj fi-1 中具有最小结束时间 fli 的活 动.设A是S的包含活动1的优化解, 其中 f1 fn,则A= 证.对A作归纳法. 当A=1时, 由引理1,命题成立. 设Ak时,命题成立. 当A=k时,由引理2,A=1A1, A1是 S2 = jS | sj f1 的优化解. 由归纳假设,A1= . 于是, A= .,贪心思想 为了选择最多的相容活动,每次选fi最小的活动,使我们能够选更多的活动,算法的设计,算法 (设f1f2.fn已
7、排序) Greedy-Activity-Selector(S, F) nlenyth(S); A1 j1 For i2 To n Do If si fj Then AAi;ji; Return A,如果结束时间已排序 T(n)=(n) 如果 结束时间未排序 T(n)=(n)+(nlogn)=(nlogn),复杂性设计,需要证明 活动选择问题具有Greedy选择性 活动选择问题具有优化子结构 算法按照Greedy选择性计算解,算法正确性证明,定理. Greedy-Activity-Selector算法能够产 生最优解. 证. Greedy-Activity-Selector算法按照引 理3的Gr
8、eedy选择性进行局部优化选 择.,5.3 Huffman codes,问题的定义 优化解的结构分析 算法设计 算法复杂性分析 算法正确性证明,二进制字符编码 每个字符用一个二进制0、1串来表示. 固定长编码 每个字符都用相同长的0、1串表示. 可变长编码 经常出现的字符用短码,不经常出现的用长码 前缀编码 无任何字符的编码是另一个字符编码的前缀,问题的定义,编码树,叶结点: 用字符及其出现频率标记,内结点: 用其子树的叶结点的频率和标记,边标记: 左边标记0,右侧边标记1,编码树T的代价 设C是字母表,cC f(c)是c在文件中出现的频率 dT(c)是叶子c在树T中的深度,即c的编码长度 T
9、的代价是编码一个文件的所有字符的代码位数: B(T)=,优化编码树问题 输入: 字母表 C = c1, c2, , cn , 频率表 F = f(c1), f(c2), ., f(cn) 输出: 具有最小B(T)的C前缀编码树,贪心思想: 循环地选择具有最低频率的两个结点, 生成一棵子树,直至形成树,我们需要证明 优化前缀树问题具有优化子结构 优化前缀树问题具有Greedy选择性,优化解的结构分析,优化子结构 引理1.设T是字母表C的优化前缀树,cC,f(c) 是c在文件中出现的频率.设x、y是T中任意 两个相邻叶结点,z是它们的父结点,则z作 为频率是f(z)=f(x)+f(y)的字符,T=
10、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)+f(y). 若T不是C的优化前缀编码树, 则必存在T,使B(T)B
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五 GreedyAlgorithm 精品 PPT 课件
链接地址:https://www.31doc.com/p-2570341.html