人工智能算法(Python语言版)PPT第4章_贪心法.pptx
《人工智能算法(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 显然,该方案是最优的,仍可能有其他最优
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 算法 Python 语言版 PPT 贪心
链接地址:https://www.31doc.com/p-21712642.html