Outline 引入:活动选择问题 贪心法 什么是贪心法 ■贪心法的适用范围 刘培 ■贪心法证明 liupei@pku.edu.cn ■几道习题 活动选择问题 活动选择问题 S={1,2,…,n}为n项活动的集合 ■Si和f分别表示活动开始和结束时间 (1 活动和活动相容当且仅当s>=f或 sj>=fi 思路: ■求两两相容的最大活动集 ■按照结束时间递增序列将活动排序,使得 满足相容关系后,按照标号从小到大选择 活动选择问题 活动选择问题 算法 Greedy select 1. n-length[S]; 2.A-{1} 3.广1; for j-2 to then a·AU{
1 贪心法 刘 培 liupei@pku.edu.cn Outline 引入：活动选择问题 什么是贪心法 贪心法的适用范围 贪心法证明 几道习题 活动选择问题 S={1,2,…,n}为n项活动的集合 si和fi分别表示活动i开始和结束时间 (1=fj或 sj>=fi 求两两相容的最大活动集 活动选择问题 思路： 按照结束时间递增序列将活动排序，使得 f1<=f2<=…<=fn 满足相容关系后，按照标号从小到大选择 1 2 3 4 5 6 活动选择问题 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 活动选择问题 算法Greedy Select 1. n←length[S]; 2. A←{1}; 3. j←1; 4. for i←2 to n 5. do if si≥fj 6. then A ← A∪{i}; 7. j ← i; 8. return A
贪心法定义 贪心法适用范围 a greedy algorithm always makes the 考虑这样一类问题 choice that looks best at the moment 会有一个最优的目标一最大/最小 That is, it makes a locally optimal 求最大活动集 choice in the hope that this choice will 会有一个或者多个约束条件 lead to a globally optimal solution 求两两相容的最大活动集 《算法导 ■需要一系列的步骤去完成一多步判断 每步选择一个任务 ■贪心法在每一步都做出一个局部最优的 不需要考虑之前或者之后的步骤一贪心选择 选择,以期在总体上仍然达到最优。 按完成时间排序,从左向右扫描,不回溯 贪心法适用范围 贪心法适用范围 ■满足优化原则的组合优化问题 ■优化原则 若满足贪心选择性质得最优解,否则得近似解 ■什么是组合优化问题 一个最优决策序列的任何子序列本身一定是 相对于子序列的初始和结束状态的最优的决 策序列 Y有穷的值集合一相容活动集A的规模{1,…n 例:从北京经过广州到海南的最短距离,肯定包 f(x)目标函数-max|Al G约束条件集合一S>=f或>=f(1< 括北京到广州的最短距离,以及广州到海南的最 短距离 ,盒在满是中家翻美使 舌动选择问题 数f(x)取得最大(小)值 贪心选择性质证明(归纳基 贪心法适用范围 础) ■贪心选择性质一正确性 设s={12…,m是活动集,活动按截止时间递 所求问题的最优解,可以通过一系列的局部 增顺序排序 最优解的选择,即贪心选择得到 ■满足贪心选择得到最优解,否则为近似解 k=1,证明存在最优解包含活动1 需要证明,一般采用数学归纳法 任取最优解AA中的活动按照截止时间递增 对选择步骤归纳 顺序排列如果A的第一个活动为子1 对问题规模归纳 令A=(4)11》由于且≤历也是最优 解,且含有1
2 贪心法定义 A greedy algorithm always makes the choice that looks best at the moment. That is , it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution. --《算法导 论》 贪心法在每一步都做出一个局部最优的 选择，以期在总体上仍然达到最优。 贪心法适用范围 考虑这样一类问题： 会有一个最优的目标—最大/最小 求最大活动集 会有一个或者多个约束条件 求两两相容的最大活动集 需要一系列的步骤去完成—多步判断 每步选择一个任务 不需要考虑之前或者之后的步骤—贪心选择 按完成时间排序，从左向右扫描，不回溯 贪心法适用范围 满足优化原则的组合优化问题 若满足贪心选择性质得最优解，否则得近似解 什么是组合优化问题 X 有穷的变量集合—活动集合S = {|1=fj或sj>=fi (1Y，并且在满足G中约束条件的前提下使得目标函 数f(x)取得最大（小）值 贪心法适用范围 优化原则 一个最优决策序列的任何子序列本身一定是 相对于子序列的初始和结束状态的最优的决 策序列 例：从北京经过广州到海南的最短距离，肯定包 括北京到广州的最短距离，以及广州到海南的最 短距离 活动选择问题 贪心法适用范围 贪心选择性质—正确性 所求问题的最优解，可以通过一系列的局部 最优解的选择，即贪心选择得到 满足贪心选择得到最优解，否则为近似解 需要证明，一般采用数学归纳法 对选择步骤归纳 对问题规模归纳 贪心选择性质证明（归纳基 础） 设S={1,2,…,n}是活动集，活动按截止时间递 增顺序排序. k=1, 证明存在最优解包含活动1. 任取最优解A, A中的活动按照截止时间递增 的顺序排列. 如果A的第一个活动为j，j≠1, 令A’= (A−{j})∪{1}, 由于f1≤fj, A’也是最优 解，且含有1
贪心选择性质证明(归纳步 部分背包问题 假设命题对k为真证明对k+1也为真 问题描述 算包盒=:了话动a…,根据归纳假设存在最 背包的重量限制为b iIES, sle n件物品,重量和价值分别为w,ⅵ,物品可以分 若425的最优解且12的请动比54米a 求满足背包重量限制的条件下,装入物品的最大 问题抽象 (题的最优a,a…,+D(e4+ 目标函数ma∑约束条件∑vx≤b 贪心思想 物品按照Ww进行排序,由高到低装入背包 其他背包问题 其他背包问题 ■考虑 ■ Loading问题 如果每种物品不止有一件(有限或无限件) n个集装箱12,…,n装上轮船,集装箱酌重 且可分割,能不能用贪心算法? 量W轮船装载重量限制为c,无体积限制 线性规划问题(目标函数和约束条件都是线 M≤c 性函数)一部分背包问题一贪心算法 ■0-1背包问题的限制形式:vi=1 整数规划问题(x均为非负整数)一一般 背包问题一搜索与剪枝/动态规划 贪心思想 将集装箱按照从轻到重排序,轻者先装 0-1规划问题-01背包问题一搜索与剪枝 证明:对问题规模进行归纳 /动态规划 经典贪心法 贪心法得到近似解 ■三个经典的贪心图算法(注意正确性证 ■地图着色问题 相邻的区域着不同的颜色,要求使用的颜色 Prim算法(最小生成树)(教材194页) 尽量少 对连接两个集合的最小边进行贪心选择 一般采用回溯法解决 Kruskal算法(最小生成树)(教材196页) 如果地图比较大,会采用贪心法求近似解 对连接两个集合的最小边进行贪心选择 ■不满足贪心选择性质,只能得到近似解 Dijkstra算法(单源最短路径)(教材187 页) ·选择下一个离单源最近的结点
3 贪心选择性质证明（归纳步 骤） 假设命题对k为真,证明对k+1也为真. 算法执行到第k步, 选择了活动i1=1, i2, …, ik, 根据归纳假设存在最 优解A包含i1= 1, i2, … , ik, A中剩下的活动选自集合S’={ i | i∈S, si≥fk},且 A= {i1, i2, … , ik}∪B, B是S’的最优解. 若不然, S’的最优解为B*, B*的活动比B多，那么B*∪{1, i2, … , ik}是S 的最优解，且比A的活动多,与A 的最优性矛盾. 根据归纳基础，存在S’的最优解B’含有S’中的第一个活动，设为 ik+1, 且|B’|=|B|, 于是 {i1 , i2, … , ik} ∪ B’={i1 , i2, … , ik, ik+1} ∪(B’-{ik+1})也 是原问题的最优解. 部分背包问题 问题描述 背包的重量限制为b n件物品，重量和价值分别为wi，vi，物品可以分 割 求满足背包重量限制的条件下，装入物品的最大 价值 问题抽象 目标函数 约束条件 贪心思想 物品按照vi/wi进行排序，由高到低装入背包 ∑= n i i i v x 1 max ∑= ≤ n i i i w x b 1 其他背包问题 考虑 如果每种物品不止有一件（有限或无限件） 且可分割，能不能用贪心算法？ 线性规划问题（目标函数和约束条件都是线 性函数） — 部分背包问题 — 贪心算法 整数规划问题（xi均为非负整数） — 一般 背包问题 — 搜索与剪枝 / 动态规划 0-1规划问题 — 0-1背包问题 — 搜索与剪枝 / 动态规划 其他背包问题 Loading问题 n个集装箱1,2,…,n 装上轮船，集装箱i的重 量wi, 轮船装载重量限制为c， 无体积限制. 问如何装使得上船的集装箱最多？不妨设 wi≤c. 0-1背包问题的限制形式 : vi=1 贪心思想 将集装箱按照从轻到重排序，轻者先装 证明：对问题规模进行归纳 经典贪心法 三个经典的贪心图算法（注意正确性证 明） Prim算法（最小生成树）（教材194页） 对连接两个集合的最小边进行贪心选择 Kruskal算法（最小生成树）（教材196页） 对连接两个集合的最小边进行贪心选择 Dijkstra算法（单源最短路径）（教材187 页） 选择下一个离单源最近的结点 贪心法得到近似解 地图着色问题 相邻的区域着不同的颜色，要求使用的颜色 尽量少 一般采用回溯法解决 如果地图比较大，会采用贪心法求近似解 不满足贪心选择性质，只能得到近似解
贪心法得到近似解 贪心法得到近似解 ■地图着色问题贪心选择 ■地图着色问题 Whle存在未被着色的区域 按1,2,345顺序进行贪心选择 选择一种新颜色C 选择一个未着色的区域A,用C着色 考察其他所有未着色区域,如果不与着色 为C的区域相邻,就用C着色 ■最优解应该为 贪心法、动态规划与回溯 习题 动态规划 贪心法 安装雷达 使用条件优化原则 多米诺性质 货心选择 多步判断 多步判断 区间覆 拆墙 选择依据子问题结果 约束条件和界 计算过程看子问题结果选择|选择后生成子问题选择后生成子问题 钓鱼 一个和多个最优解一个最优和近似解 关键问题遂推方程 贪心选择性质证明 空问复杂度高 时向复杂度高 近似解的误差估计 安装雷达1328 安装雷达1328 ■海上有N个扫描点 ■对什么进行贪心选择?怎么排序? 雷达扫描范围d 按横坐标排序从左到右扫描? ■至少要安装几个雷达才能将N个点都覆盖 ++9 ,.个
4 贪心法得到近似解 地图着色问题贪心选择 While 存在未被着色的区域 选择一种新颜色C 选择一个未着色的区域A，用C着色 考察其他所有未着色区域，如果不与着色 为C的区域相邻，就用C着色 贪心法得到近似解 地图着色问题 按1,2,3,4,5顺序进行贪心选择 最优解应该为 1 5 2 4 3 1 5 2 4 3 贪心法、动态规划与回溯 贪心选择性质证明 近似解的误差估计 设定代价函数 时间复杂度高 递推方程 空间复杂度高 关键问题 解 一个最优解 一个和多个最优解 一个最优和近似解 数据结构 二维表 树、队列 线性表 选择后生成子问题 自顶向下 选择后生成子问题 自顶向下 看子问题结果选择 自底向上 计算过程 选择依据 子问题结果 约束条件和界 局部最优性质 贪心选择 优化原则 多步判断 多米诺性质 多步判断 优化原则 多步判断 使用条件 技术 动态规划 分支估界 贪心法 习题 安装雷达 区间覆盖 拆墙 钓鱼 安装雷达 1328 海上有N个扫描点 雷达扫描范围d 至少要安装几个雷达才能将N个点都覆盖 住 安装雷达 1328 对什么进行贪心选择？怎么排序？ 按横坐标排序从左到右扫描？
安装雷达1328 区间覆盖 ■能被雷达覆盖的区间 ■数轴上有n个点,至少用几个单位长度区 间才能将他们覆盖? ■对什么进行贪心选择?怎么排序? 拆墙1230 拆墙1230 ■魔术师表演穿墙012345 对什么进行贪心?如何排序 ■墙都是水平的 拆哪面墙? ■最多能穿k面墙 ■最长的? ■最少拆几面墙才 ■跨越不安全的列最多的? 能保证魔术师安 全通过? 拆墙1230 钓鱼1042 ■拆掉右端点最靠右的墙,为什么? John准备去钓鱼 有n个湖,它们中间依次有一段路程,消耗弹位时间 每个湖始单位时间(5分钟)可钓到鱼的数量为m 然后每个单位时间鱼量减少 5
5 安装雷达 1328 能被雷达覆盖的区间 区间覆盖 数轴上有n个点，至少用几个单位长度区 间才能将他们覆盖？ 对什么进行贪心选择？怎么排序？ 拆墙 1230 魔术师表演穿墙 墙都是水平的 最多能穿k面墙 最少拆几面墙才 能保证魔术师安 全通过？ 拆墙 1230 对什么进行贪心？如何排序？ 拆哪面墙？ 最长的？ 跨越不安全的列最多的？ 拆墙 1230 拆掉右端点最靠右的墙，为什么？ 钓鱼 1042 John准备去钓鱼。 有n个湖，它们中间依次有一段路程，消耗t[i]单位时间 每个湖i初始单位时间（5分钟）可钓到鱼的数量为f[i] 然后每个单位时间鱼量减少d[i]
钓鱼1042 钓鱼1042 问题: 方法提示 如何设计路线和停留时间,使得钓到的鱼数量 以每一个湖做为终止点,分别采用贪心法 最多? 1.可用时间=总时间一路程时间 如何使用贪心法来解决这道题? 每个单位时间挑选前湖中鱼量最大的(排序) 反复2,直到可用时间用尽 对什么进行排序?对什么进行贪心选择? 挑出n个结果中最大的做为最后结果 钓鱼1042 ■注意细节 可能有的湖中鱼的递减量为0 可能有多个结果,根据题意取舍 谢谢大家 排序:C采用qot(不保证相对序) C++/STL用sort或者 stable sort 请大家到PO上试一试
6 钓鱼 1042 问题： 如何设计路线和停留时间，使得钓到的鱼数量 最多？ 如何使用贪心法来解决这道题？ 对什么进行排序？对什么进行贪心选择？ 钓鱼 1042 方法提示： 以每一个湖i做为终止点，分别采用贪心法。 1. 可用时间 = 总时间 – 路程时间 2. 每个单位时间挑选前i个湖中鱼量最大的（排序） 3. 反复2，直到可用时间用尽 挑出n个结果中最大的做为最后结果 钓鱼 1042 注意细节： 可能有的湖中鱼的递减量为0 可能有多个结果，根据题意取舍 排序： C采用qsort (不保证相对序) C++/STL用sort或者stable_sort 请大家到POJ上试一试 谢谢大家
