概要 Lecture 4 ·动态规划回顾 Greedy algorithm ·活动问题选择分析 ·贪婪算法要点 清华大学 ·拟阵概念 宋斌恒 动态规划要点回顾 最优子结构的关键步骤 ·最优子结构 1.关键过程(点)选择,例如 生产安排 装配问题选择经过的装配站 矩阵链乘 乘法问题选择括号分界线 -LCS LCS问题如何确定子问题 Print Neatly Print neatly问题选择在什么地方分行做完选 最优二叉搜索树 择后留下若干子问题 续 Greedy Algorithm 2.最优选择成立假设:只需要假设其中的关 Sample1.活动选择问题 键点假设成立即可,如何选择、先不管 Several competing activities that require 3.子问题空间:在上述选择决定后,留下什 exclusive use of common resources(Same 么样的子问题才能保证上述问题的选择是 place at a fixed period of time), with the goal 最优的 of selecting a maximum-size set of mutually compatible activities that wish to use a 4.证明你的方案是最优的,方法:" Cut-and resource(a period of time in the place)
1 Lecture 4. Greedy Algorithm 清华大学 宋斌恒 清华大学 软件学院 宋斌恒 2 概要 •动态规划回顾 •活动问题选择分析 •贪婪算法要点 •拟阵概念 清华大学 软件学院 宋斌恒 3 动态规划要点回顾 •最优子结构 –生产安排 –矩阵链乘 –LCS –Print Neatly –最优二叉搜索树 清华大学 软件学院 宋斌恒 4 最优子结构的关键步骤 1. 关键过程（点）选择，例如 – 装配问题选择经过的装配站 – 乘法问题选择括号分界线 – LCS问题如何确定子问题 – Print neatly 问题选择在什么地方分行做完选 择后留下若干子问题 清华大学 软件学院 宋斌恒 5 续 2. 最优选择成立假设：只需要假设其中的关 键点假设成立即可，如何选择、先不管 3. 子问题空间：在上述选择决定后，留下什 么样的子问题才能保证上述问题的选择是 最优的 4. 证明你的方案是最优的，方法：“Cut-andpaste” 清华大学 软件学院 宋斌恒 6 Greedy Algorithm •Sample 1. 活动选择问题 –Several competing activities that require exclusive use of common resources (Same place at a fixed period of time), with the goal is of selecting a maximum -size set of mutually compatible activities that wish to use a resource (a period of time in the place)
Mathematical model Definition of solution Each activity a; has a start time S, and a subset a of s is a solution if all the finish time f where0≤sf<∝ activities in A are mutually compatible · Compatible【相容】 activities: We call two We call a solution A is optimal if it is a activities are compatible if the two intervals does not overlap (i.e, ai, a, are compatible solution whose size is one of the largest is≥fors ·S={a1,a2…an} Problem: The activity-selection problem is to select a maximum- size subset of s ctivities An instance of the problem 按照动态规划步骤分析 S={14).[35),[0.6),[57).[3.8),[59) 1.选择:选什么?我们选择必定有一个活动在 最优解中假设其为ak [6,10),[8,11),8,12,[2,13),[1214) 2.子问题空间, Let ax be in the optimal solution, how to construct the sub-problem paces?第一部分:在a开始前结束的活动 Notice! The elements are sorted by the 成的问题,第二部分:在a结束后开始的 end time 活动构成的问题,最优解由第一部分的最优 解十{a}+第二部分的最优解。 3.正确吗?如果有一个最优解,从中取出 活动,而后把此最优解分成两部分,问其 的第一部分是第一个子问题的最优解吗? 最优子问题 人工活动 根据上面的分析我们构造以下子问题: Adding two fictitious activities ao and an+1 LetS= (ak in S:f≤sfk≤ si, then Si is the such that fo=0 and Sn+1 = oo, then S=So.n+1 subset of s that can start after activity a ·原问题S=Sont! finishes and finish before activity a starts 原问题是什么?
2 清华大学 软件学院 宋斌恒 7 Mathematical model •Each activity ai has a start time si and finish time f i , where 0≤si<f i<∞. • Compatible【相容】 activities: We call two activities are compatible if the two intervals does not overlap (i.e., ai , aj are compatible if si≥f j or sj≥f i ) • S={a1 ,a2 ,… ,an } • Problem: The activity-selection problem is to select a maximum-size subset of S contains mutually compatible activities 清华大学 软件学院 宋斌恒 8 Definition of Solution •A subset A of S is a solution if all the activities in A are mutually compatible. •We call a solution A is optimal if it is a solution whose size is one of the largest. 清华大学 软件学院 宋斌恒 9 An instance of the problem •S={[1,4), [3,5), [0,6), [5,7), [3,8), [5,9), [6,10), [8,11), [8,12), [2,13), [12,14)} •Notice! The elements are sorted by the end time 清华大学 软件学院 宋斌恒 10 按照动态规划步骤分析 1. 选择：选什么？我们选择必定有一个活动在 最优解中,假设其为ak 2. 子问题空间，Let ak be in the optimal solution, how to construct the sub-problem spaces? 第一部分：在ak开始前结束的活动 构成的问题，第二部分：在ak结束后开始的 活动构成的问题，最优解由第一部分的最优 解＋{ak }＋第二部分的最优解。 3. 正确吗？如果有一个最优解，从中取出一个 活动，而后把此最优解分成两部分，问其中 的第一部分是第一个子问题的最优解吗？ 清华大学 软件学院 宋斌恒 11 最优子问题 •根据上面的分析我们构造以下子问题： •Let Sij={ak in S: f i≤sk<fk≤sj }, then Sij is the subset of S that can start after activity ai finishes and finish before activity aj starts •原问题是什么？ 清华大学 软件学院 宋斌恒 12 人工活动 •Adding two fictitious activities a0 and an+1 such that f0=0 and sn+1 = ∞, then S=S0,n+1 • 原问题S=S0,n+1！
Assumption Properties Assumption: the activities are sorted by its S=o whenever ij finish time If we sorted the activities in monotonically ·f6≤f1≤f2≤…≤f<fn+1 creasing order of finish time then the ib problem space is a subset of the Si] for all ·我们能否做到?假设合理否?当然可以, 0≤j≤n+1 我们能够通过排序来完成 Suppose A is an optimal solution of problem Si and ak is in ai then the solutions Ak to Sk and Ay to Sw used within this optimal solution to Si must be optimal as well 最优解的一部分是相关子问题的最 optimal solution can be 优解 constructed by optimal solutions of subproblems 问题的进一步明确:设S是子问题,A是其 最优解,A是A中的一个元素,S和S是 If ak is contains in an optimal solution of Si 相应的子问题,A和A是A按照A前发生 than any optimal solution Ayj which 和A后发生划分的集合,问:A不和A是相 contains a can be expressed by 应的子问题的解吗?是他的最优解吗? Aj=Ak U(akUA "cut-and- paste method Where Ak and Ai are optimal solutions for If a solution Aik to Sik contians more element SK and Ski than Ak we could cut out Ak from A; and paste in Aik, thus producing an anothe onverting a dynamIc A recursive solution programming solution to a greedy solution Let c[ i, j] be the number of the activities in ar Theorem 16 optimal solution to sij, we have c[i,J=0 henever s=Φ; Consider any nonempty subproblem Sy, and let am be the activity in S, with the earliest finish time: Fm= min(fk: ak in S fS=φ c[i,]= Activity am is used in some maximum-size subset max]+4k+l}fS≠ of mutually compatible activities of Sy
3 清华大学 软件学院 宋斌恒 13 Assumption • Assumption: the activities are sorted by its finish time: • f0≤f1≤f2≤… ≤fn<fn+1 • 我们能否做到？假设合理否？当然可以， 我们能够通过排序来完成 清华大学 软件学院 宋斌恒 14 Properties • Sij=0 whenever i≥j • If we sorted the activities in monotonically increasing order of finish time, then the subproblem space is a subset of the {Sij} for all 0≤i<j≤n+1. • Suppose Aij is an optimal solution of problem Sij, and ak is in Aij, then the solutions Ai k to Si k and Akj to Skj used within this optimal solution to Sij must be optimal as well. • Notice! The definition of Ai k in the above statment 清华大学 软件学院 宋斌恒 15 最优解的一部分是相关子问题的最 优解 •问题的进一步明确：设Sij是子问题，Aij是其 最优解，Ak是Aij中的一个元素，Sik和Skj是 相应的子问题，Aik和Akj是Aij按照Ak前发生 和Ak后发生划分的集合，问： Aik和Akj是相 应的子问题的解吗？是他的最优解吗？ •“cut-and-paste”method: –If a solution A’ ik to Si k contians more elements than Ai k, we could cut out Ai k from Aij and paste in A’ ik, thus producing an another solution to Sij which has more activities than Aij, which produces a contradiction! 清华大学 软件学院 宋斌恒 16 Optimal solution can be constructed by optimal solutions of subproblems •If ak is contains in an optimal solution of Sij than any optimal solution Aij which contains ak can be expressed by •Aij = Aik U {ak } U Akj •Where Aik and Akj are optimal solutions for Sik and Skj A recursive solution • Let c[ i, j] be the number of the activities in an optimal solution to Sij, we have c[ i, j] = 0 whenever Sij = Φ; ïî ï í ì + + ¹ = = < < f f ij i k j ij c i k c k j S S c i j max{ [ , ] [ , ] 1} if 0 if [ , ] Converting a dynamicprogramming solution to a greedy solution •Theorem 16.1 –Consider any nonempty subproblem Sij, and let am be the activity in Sij with the earliest finish time: Fm = min{fk : ak in Sij} –Then •Activity a m is used in some maximum-size subset of mutually compatible activities of Sij •The subproblem Sim is empty
Proof of the theorem Why theorem 16.1 is valuable? The second part of the theorem is trivial Reduce the subproblems To prove the first part, let A, is an optim We can compute the optimal solution in a solution of Sj, and order the activities in A j top-down fashion, rather than the bottom in monotonically increasing order of finish up manner used in dynamic programming time. Let ax be the first activity in Aj, if ak=am, then we have done, else we can replace a with am in Aj, and it changes to another solution! It is optimal too The solution constructing 课堂练习 procedure Find the activity ax which has the earliest 实例:S={(09),(1,2),(1,3),(2,5),(49) finish time in So.n+1, and it left a problem (58),(7,9),(8,12),(7,11),(9,11),(11,12)} Sk.n+, then one of the optimal solution is 写出递归算法,并模拟算法的实现 faJU An+. Where An+1 is the optimal solution of S 写出叠代(递推)算法,并模拟实现。 Find the activity as which has the earliest finish time in A,n+1… Problems on Greedy Elements of the greedy strategy Algorithm Not all greedy algorithm generate the 1. Determine the optimal substructure of the optimal solution if we choose the least duration activity as our activity selection 2. Develop a recursive solution strategy in the activity-selection problem 3. Prove that at any stage of the recursion, one of the optimal choices is the greedy choice. Thus then it does not always create the optimal it is always safe to make the greedy choice solution Show that all but one of the subproblems nother greedy algorithm for induced by having made the greedy choice are ction problem? empty 6. Convert it to an iterative one
4 Proof of the theorem •The second part of the theorem is trivial. •To prove the first part, let Aij is an optimal solution of Sij, and order the activities in Aij in monotonically increasing order of finish time. Let ak be the first activity in Aij, if ak=am, then we have done, else we can replace ak with am in Aij, and it changes to another solution! It is optimal too! Why theorem 16.1 is valuable? •Reduce the subproblems •We can compute the optimal solution in a top-down fashion, rather than the bottomup manner used in dynamic programming. 清华大学 软件学院 宋斌恒 21 The solution constructing procedure •Find the activity ak which has the earliest finish time in S0,n+1, and it left a problem Sk,n+1, then one of the optimal solution is {ak }U Ak,n+1. Where Ak,n+1 is the optimal solution of Sk,n+1 •Find the activity as which has the earliest finish time in Ak, n+1… … 清华大学 软件学院 宋斌恒 22 课堂练习 •实例：S={(0,9), (1,2), (1,3), (2,5), (4,9), (5,8), (7,9), (8,12), (7,11), (9,11), (11,12)} •写出递归算法，并模拟算法的实现， •写出叠代（递推）算法，并模拟实现。 Problems on Greedy Algorithm •Not all greedy algorithm generate the optimal solution: if we choose the least duration activity as our activity selection strategy in the activity-selection problem, then it does not always create the optimal solution •Can you find another greedy algorithm for the activity-selection problem? Elements of the greedy strategy 1. Determine the optimal substructure of the problem 2. Develop a recursive solution 3. Prove that at any stage of the recursion, one of the optimal choices is the greedy choice. Thus, it is always safe to make the greedy choice 4. Show that all but one of the subproblems induced by having made the greedy choice are empty 5. Develop a recursive algorithm 6. Convert it to an iterative one
Greedy choice property Optimal substructure To obtain optimal solution for an optimal Optimal substructure: an optimal solution problem, it needs a greedy-choice to a problem contains within it optimal property: A globally optimal solutio on can solutions to the subproblems e arrived at by making a locally optimal (greedy) choice Greedy versus dynamic programmIng 背包问题 Greedy is sufficient ·背包问题:一个包容积有限,每件物体有 Greedy does not work but dynami 不同容积和价值,如何装包使得价值最 programming works 大? Examples ·如果物体不能分割,其最优装包问题叫0 0-1 knapsack problem 1背包问题 Fractional knapsack problem 如果物体可以分割,其最优装包问题叫分 数背包问题 背包问题的贪婪算法 问题实例:包容积50L,3类东西:第 种:60￥、10L、1件;第二种:100￥ 20L、1件;第三种:120￥、30L、1件 贪婪算法 单位容积价格最大的:第一种1件、第二种1 件、第三种23件,价值60+100+80=240￥ 如果0一1背包问题,则贪婪算法只能收获 160￥,而明显的第二种1件+第三种1件可以 装220￥
5 Greedy choice property •To obtain optimal solution for an optimal problem, it needs a greedy-choice property: A globally optimal solution can be arrived at by making a locally optimal (greedy) choice. Optimal substructure •Optimal substructure: an optimal solution to a problem contains within it optimal solutions to the subproblems Greedy versus dynamic programming •Greedy is sufficient •Greedy does not work but dynamic programming works. •Examples –0-1 knapsack problem –Fractional knapsack problem 清华大学 软件学院 宋斌恒 28 背包问题 •背包问题：一个包容积有限，每件物体有 不同容积和价值，如何装包使得价值最 大？ •如果物体不能分割，其最优装包问题叫0－ 1背包问题 •如果物体可以分割，其最优装包问题叫分 数背包问题 清华大学 软件学院 宋斌恒 29 背包问题的贪婪算法 •问题实例：包容积50L，3类东西：第一 种：60￥、10L、1件；第二种：100￥、 20L、1件；第三种：120￥、30L、1件。 •贪婪算法： –单位容积价格最大的：第一种1件、第二种1 件、第三种2/3件，价值60＋100＋80＝240￥ –如果0－1背包问题，则贪婪算法只能收获 160￥，而明显的第二种1件＋第三种1件可以 装220￥