数据结构与算法实习 算法之三:贪心法 北京大学信息科学技术学院 主讲:张铭、郝丹 zhang lat] net pku. edu.cn http://wwwipkpkueducn/pkujpk/course/siig/shixil 20118 张铭赵海燕王腾蛟宋国杰,《数据结构与算法实验教程》 (国家十一五规划教材),高教社2011年1月
数据结构与算法实习 ——算法之三：贪心法 北京大学信息科学技术学院 主讲：张 铭、郝 丹 mzhang [at] net.pku.edu.cn http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/shixi/ 2011.8 张铭 赵海燕 王腾蛟 宋国杰，《数据结构与算法实验教程》 （国家十一五规划教材），高教社2011年1月
Outline 引入:活动选择问题 贪心法的基本概念 贪心法的适用范围 贪心法证明 ■几道习题
Outline ◼ 引入：活动选择问题 ◼ 贪心法的基本概念 ◼ 贪心法的适用范围 ◼ 贪心法证明 ◼ 几道习题
活动选择问题 nS={12…n}为n项活动的集合 S和f分别表示活动开始和结束时间(1≤i≤n) 活动和活动相容当且仅当s≥f或S12f 相容 不相容 ■目标:求两两相容的最大活动集
活动选择问题 ◼ S={1,2,…,n}为n项活动的集合 ◼ si和fi分别表示活动i开始和结束时间(1 ≤ i ≤ n) ◼ 活动i和活动j相容当且仅当si ≥ fj或sj ≥ fi ◼ 相容 ◼ 不相容 ◼ 目标：求两两相容的最大活动集 1 2 5 6
活动选择问题 ■思路: 按照结束时间递增序列将活动排序,使得 1,6,2,53,4 满足相容关系后,在序列中从左到右选择
活动选择问题 ◼ 思路： ◼ 按照结束时间递增序列将活动排序，使得 f1 ≤ f2 ≤… ≤ fn ◼ 1, 6, 2, 5, 3, 4 ◼ 满足相容关系后，在序列中从左到右选择 1 2 3 4 5 6
活动选择问题
活动选择问题 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
nS={12…n}为n项活动的集合 s和分别表示活动开始和结束时间(1≤i≤n) 活动和活动相容当且仅当s≥f或S12f i1234567891011 s1031355688212 f6548791011121314 求出两两相容的最大活动集合
◼ S={1,2,…,n}为n项活动的集合 ◼ si和fi分别表示活动i开始和结束时间(1 ≤ i ≤ n) ◼ 活动i和活动j相容当且仅当si ≥ fj或sj ≥ fi ◼ 求出两两相容的最大活动集合 s i i f i 1 2 3 4 5 6 7 8 9 10 11 si 0 3 1 3 5 5 6 8 8 2 12 fi 6 5 4 8 7 9 10 11 12 13 14
活动选择问题 ■按照结束时间f排序 1234567891011 s;130535688212 41567891011121314 两两相容的最大活动集合为 A={14811},原来未排序的{358 11
活动选择问题 ◼ 按照结束时间fi 排序 ◼ 两两相容的最大活动集合为 ◼ A = {1, 4, 8, 11}，原来未排序的 {3, 5, 8, 11} i 1 2 3 4 5 6 7 8 9 10 11 si 1 3 0 5 3 5 6 8 8 2 12 fi 4 5 6 7 8 9 10 11 12 13 14
活动选择问题 算法 Greedy select 1.//engthS 2.A-{1} 3.产1; 4.for产-2to 567 do if si then a←AU{Y a8. return A
活动选择问题 算法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. 《算法导论》 贪心法在每一步都做出一个局部最优的 选择,以期在总体上仍然达到最优
贪心法定义 ◼ 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. --《算法导论》 ◼ 贪心法在每一步都做出一个局部最优的 选择，以期在总体上仍然达到最优
最优选择问题 最优选择问题 N个输入 解为这N个输入的某个子集(或其他变体) 约束条件→可行解 目标函数,用于评判可行解的优劣→最优解 ■求解方法:根据约束条件和目标函数的数学模型的特 性或求解问题方法的不同进而细分为 (非)线性规划、整数规划 动态规划 回溯法 种更直接的求解方法 贪心算法
最优选择问题 ◼ 最优选择问题 ◼ N个输入 ◼ 解为这N个输入的某个子集（或其他变体） ◼ 约束条件→可行解 ◼ 目标函数，用于评判可行解的优劣→最优解 ◼ 求解方法：根据约束条件和目标函数的数学模型的特 性或求解问题方法的不同进而细分为 ◼ (非)线性规划、整数规划 ◼ 动态规划 ◼ 回溯法 ◼ 一种更直接的求解方法 ◼ 贪心算法