《人工智能算法（Python语言版）PPT第4章_贪心法.pptx》由会员分享，可在线阅读，更多相关《人工智能算法（Python语言版）PPT第4章_贪心法.pptx（16页珍藏版）》请在三一文库上搜索。
1、提纲w 应用背景和动机w 贪心算法的基本思想w 哈夫曼编码w 总结应用背景和动机(1)背景：背景：主播带货已成为了一种新的产品推销手段。为响应国家脱贫攻坚和乡村振兴战略，边远山区的地方政府也采取主播带货的方式推广农产品。例如例如：假设一批农产品要被想被大众熟知，则其影响因子需要达到1.3，现有3类主播，其中A类主播可帮助农产品提高0.4的影响因子，B类主播可帮助农产品提高0.3的影响因子，C类主播可帮助农产品提高0.1的影响因子。问题：问题：应该如何安排主播带货，能够在最少的主播数量下帮助政府使得该农产品被大众熟知？直观的方案直观的方案：尽量选择影响因子高的主播，即选择3名A类主播和1名C类主
2、播，就可在最少的主播数量下让这批农产品的影响因子达到期望值。应用背景和动机(2)w 优化问题（优化问题（Optimization problem）不仅要找到答案，且要找到最佳答案w 贪心算法（贪心算法（Greedy algorithm）有时对优化问题能有较好的解决方案w 贪心算法分阶段执行，每一个阶段：贪心算法分阶段执行，每一个阶段：-当考虑做何种选择时，只考虑对当前问题最佳的选择，而不考虑其子问题的结果-希望通过每一个步骤的局部最优（Local optimum）而得到全局最优（Global optimum）-未必能得到最优解应用背景和动机(3)w 运行9个作业，其时间分别为3,5,6,10,
3、11,14,15,18,20 w 共有3个处理器，可执行这些作业w 按照最长时间作业优先最长时间作业优先的原则，将作业安排到空闲处理器201815141110653P1P2P3w 完成作业所需时间为18+11+6=35w 这一方案并不差，但是可能有更好的方案引例：引例：多机调度应用背景和动机(4)若按照最短时间作业优先最短时间作业优先的原则，结果如何？201815141110653P1P2P3w 以上方案并不是一个好的方案，完成作业所需时间为6+14+20=40 w 注意到：贪心算法本身能高效地执行每个阶段所需：选择当前最小或最大者应用背景和动机(5)w 显然，该方案是最优的，仍可能有其他最优
4、方案w 如何得到以上最优方案？-尝试所有作业安排给处理器的可能方案，选择最短完成时间 -需指数计算时间更好的方案：更好的方案：201815141110653P1P2P3结论：结论：贪心算法具有较高效率，其答案从实际应用的角度看已足够好贪心算法具有较高效率，其答案从实际应用的角度看已足够好提纲w 应用背景和动机w 贪心算法的基本思想w 哈夫曼编码w 总结贪心算法的基本思想1、贪心选择性质、贪心选择性质 所求问题的整体最优解整体最优解，希望通过一系列局部最优局部最优的选择 （贪心选择）贪心算法可行的第一个基本要素 通常以自顶向下自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就
5、将所求问题简化为规模更小的子问题 每一步对目前构造的部分解做一个扩展，满足：可行（满足约束）、可行（满足约束）、局部最优、不可取消局部最优、不可取消（贪心算法与动态规划算法的主要区别）2、最优子结构性质、最优子结构性质 问题的最优解包含其子问题的最优解证明贪心算法的正确性（针对最优化问题的求解）证明贪心算法的正确性（针对最优化问题的求解）：-证明每一步所作的贪心选择最终导致问题的整体最优解-数学归纳法提纲w 应用背景和动机w 贪心算法的基本思想w 哈夫曼编码w 总结哈夫曼编码(1)w 背景背景 -哈夫曼编码广泛地用于数据文件压缩 -压缩率通常在20%90%之间（变长码）-哈夫曼编码算法用字符在
6、文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式 -给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长 w 前缀码前缀码 -尽可能多地压缩文件、源文件很容易被重建 -任一字符的代码(0,1序列)都不是其他字符代码的前缀完全二叉树T -满足前缀约束，则编码无二义性 -平均码长：()()()TcCB Tf c dc字符c出现的频率为f(c),在T中的深度为dT(c)哈夫曼编码(2)w 哈夫曼编码（Huffman encoding）算法为贪心法w 选择并合并最小出现频度的两个数字w 平均编码长度 0.22*2+0.12*3+0.24*2+0.06*4+0.
7、27*2+0.09*4 =2.42哈夫曼编码能得到最优编码22 12 24 6 27 9 A B C D E F152746100A=00B=100C=01D=1010E=11F=101154编码结果哈夫曼编码(3)哈夫曼编码(4)w 哈夫曼编码算法正确性证明的思路哈夫曼编码算法正确性证明的思路 对最优前缀码二叉树T作修改得T，T表示对C做出贪心选择得到的最优前缀码，x和y是T中最深叶子且为兄弟（树T与T具有相等的平均码长）。xybcTbcxyT T中：-f(b)f(c)f(x)f(y)-x和y是具有最小频 率的两个字符 f(x)f(b)f(y)f(c)T 是对C做出贪心选择的前缀编码树提纲w 应用背景和动机w 贪心算法的基本思想w 哈夫曼编码w 总结总结w 应用背景和动机w 贪心算法的基本思想和关键 -贪心选择性质 -最优子结构性质 -贪心选择标准w 贪心算法的重要实例：哈夫曼编码w 贪心算法的正确性证明思路：数学归纳法结语谢谢！