算法设计与分析第05章贪心算法.PPT

上传人:国*** 文档编号:943795 上传时间:2018-11-09 格式:PPT 页数:21 大小:195KB
下载 相关 举报
算法设计与分析第05章贪心算法.PPT_第1页
第1页 / 共21页
算法设计与分析第05章贪心算法.PPT_第2页
第2页 / 共21页
算法设计与分析第05章贪心算法.PPT_第3页
第3页 / 共21页
算法设计与分析第05章贪心算法.PPT_第4页
第4页 / 共21页
算法设计与分析第05章贪心算法.PPT_第5页
第5页 / 共21页
点击查看更多>>
资源描述

1、 算法设计与分析 第 05章 贪心算法第05章贪心算法基本思想n 通过作出在当前看来最优的选择(贪心选择),将原问题规模缩小,如此反复,直至得到最终解。n 贪心算法并非对所有问题都能得到整体最优解。第05章贪心算法活动安排问题n 设有 n个活动 E=e1, e2, , en, 其中每个活动都需要使用某一资源,而在同一时间内该资源只能由一个活动使用,每个活动都有开始时间 si和结束时间 fi(sifi), 若 ei和 ej满足 sifj或 sjfi, 则称这两个活动相容,要求找出最多相容活动集合 A。第05章贪心算法活动安排问题n 贪心解法: 将所有活动按结束时间排序,得到活动集合 E=e1,e

2、2en; 先将 e1选入结果集合 A中,即 A=e1; 依次扫描每一个活动 ei:如果 ei的开始时间晚于最后一个选入 A的活动 ej的结束时间,则将 ei选入 A中,否则放弃 ei;第05章贪心算法活动安排问题n 解法证明:n 若 E=e1,e2en是按结束时间排序的活动集合,则 e1具有最早的结束时间,设存在一个最优安排 A不包含 e1,并以 ei开始,则易见:A-ei e1也是最优的活动安排;依此类推。第05章贪心算法i si fi1 1 42 3 53 0 64 5 75 3 86 5 97 6 108 8 119 8 1210 2 1311 12 140 1 2 3 4 5 6 7

3、8 9 10 11 12 13 14结果:选中的任务为: 1、 4、 8、 11第05章贪心算法贪心算法的基本要素n 1、贪心选择性质n 所求问题的整体最优解可由一系列局部最优选择得到;n 动态规划是由子问题的解得到当前问题的解;贪心算法则是由当前问题的局部最优解导出子问题;n 确定一个问题是否具有贪心选择性质,需要证明问题的一个整体最优解是从贪心选择开始的;n 2、最优子结构性质n 通过局部最优选择,原问题将被化简为类似的子问题;亦即是说,整体最优解中包含了子问题的最优解;第05章贪心算法背包问题n 有一容量为 W的背包,和单价分别为 vi的物品块(均为单位体积)各 ni块, i=1n; 问

4、每种物品应各选择多少块装入背包中,使得背包中的总价值最大?第05章贪心算法0-1背包问题n 有一容量为 W的背包,和一批体积分别为 wi, 价值为 vi的物品, i=1n; 问将哪些物品装入背包,使得背包中的总价值最大?n 0-1背包问题不满足最优子结构性质,不能用贪心法来求解,而应用分治法求解。分治规则为:S(w1.n, v1.n, W) = maxS(w1.n-1, v1.n-1, W-wn)+vn, S(w1.n-1, v1.n-1, W)第05章贪心算法哈夫曼算法的证明n 贪心选择性质的证明n 若叶结点 x,y是被选中合并的结点,即 x,y具有最小权值,则n 1. x、 y是结果树上深度最大的两个结点,且互为兄弟;n 2. 必存在最优二叉树以 x,y为深度最大的两个结点,且互为兄弟(编码最长,且只有最后一位编码不同);n 证明:显然,总可通过交换 x,y到最深的一对兄弟结点,得到满足条件的最优二叉树;

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 重点行业资料库 > 1

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。