《算法设计与分析》课件 第6章 贪心算法_第1页
《算法设计与分析》课件 第6章 贪心算法_第2页
《算法设计与分析》课件 第6章 贪心算法_第3页
《算法设计与分析》课件 第6章 贪心算法_第4页
《算法设计与分析》课件 第6章 贪心算法_第5页
已阅读5页，还剩39页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

算法设计与分析贪心算法主要内容基本概念小数背包和0-1背包最小生成树霍夫曼编码1基本概念是指算法每次做选择的时是‘贪心’的，也就是尽量选择从目前看来是最好的如旅行商问中，设目前处于城市ci，那么就选择一条从ci到其他城市(还没有的城市)最短的边局部最优选择，并不一定能达到全局最优对某些问题是可以得到全局最优解，但对另外一些问题是无法获得全局最优解的1例子：钱币兑换1钱币兑换：动态规划步骤11钱币兑换：动态规划步骤21钱币兑换：动态规划步骤31钱币兑换：动态规划步骤41钱币兑换贪心算法先兑换大面额的硬币，只有在大面额的硬币无法兑换时，才兑换小面额的硬币1钱币兑换贪心算法和动态规划1贪心解是最优解吗？需要证明：贪心算法每次选出的解都属于最优解集合替换法归纳法1贪心解是最优解吗？替换法用贪心算法得出的解(x1,x2,···,xn)和最优解(y1,y2,···,yn)中的元素依次进行比较，如果元素xi

和yi

相同，则将最优解中的yi替换成xi，显然替换后的解还是最优解;如果不同，还是要将yi

替换成xi，但这时，还需要证明替换后的解依然是最优解1贪心解是最优解吗？归纳法贪心选择是正确的

问题具有最优子结构性质2小数背包2小数背包2小数背包2小数背包小数背包贪心算法的正确性证明：替换法设物品都已经按照性价比排好，并设X=(x1,x2,···,xk,xk+1,···,xn)是贪心算法得出的解，其中0≤xi≤1设最优解为Y=(y1,y2,···,yn)，其中0≤yi≤1找到第一个不相同的元素j，xj

≠yj

2小数背包2小数背包2

0-1背包贪心算法不一定能够得出0-1背包的最优解3最小生成树3最小生成树3最小生成树：Kruskal算法3最小生成树：Kruskal算法3

Kruskal算法对边排序(语句7)复杂度为O(mlogm)，第二个for循环(语句8-13)执行m次，循环体内的FIND语句(语句9)的复杂度为O(logn)，即第二个for循环的复杂度为O(mlogn)，所以算法总复杂度为O(mlogm+mlogn)=O(mlogm)3

最小生成树3

最小生成树3

最小生成树3

最小生成树：Prim算法3

最小生成树：Prim算法3

最小生成树：Prim算法4霍夫曼编码数据压缩应用网络、磁盘数据压缩减少数据传输量减少数据存储量.霍夫曼编码广泛的应用在数据压缩，可节省约20%-90%的数据量4霍夫曼编码4霍夫曼编码4霍夫曼编码定长和变长编码形成的编码树最优编码树，每个非叶子节点都有两个子节点4霍夫曼编码最优编码树的每个节点都有两个节点4霍夫曼编码前缀码：没有任何码字是其他码字的前缀编码：将每个码字连接起来即可解码需要从一串编码中解码出每个码字。简单，因为没有重复的前缀01101000，很容易解码出为单词‘bad’霍夫曼编码是前缀码4霍夫曼编码：算法流程4霍夫曼编码：算法流程因步骤3要重复n−1次，每次都需排序，复杂度为O(n2

logn)如果将A中的元素按照频率组织成最小堆，则取两个频率最低元素的复杂度为logn，插入一个合并后元素的复杂

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论