1 Lecture 4. Greedy Algorithm 清华大学清华大学 宋斌恒宋斌恒 清华大学清华大学 软件学院 宋斌恒 2 概要概要 ?动态规划回顾 ?活动问题选择分析 ?贪婪算法要点 ?拟阵概念 清华大学清华大学 软件学院 宋斌恒 3 动态规划要点回顾动态规划要点回顾 ?最优子结构 –生产安排 –矩阵链乘 –LCS –Print Neatly –最优二叉搜索树 清华大学清华大学 软件学院 宋斌恒 4 最优子结构的关键步骤最优子结构的关键步骤 1. 关键过程 （ 点 ） 选择 ， 例如 – 装配问题选择经过的装配站 – 乘法问题选择括号分界线 – LCS问题如何确定子问题 – Print neatly 问题选择在什么地方分行做完选 择后留下若干子问题 清华大学清华大学 软件学院 宋斌恒 5 续续 2. 最优选择成立假设 ： 只需要假设其中的关 键点假设成立即可 ， 如何选择 、 先不管 3. 子问题空间 ： 在上述选择决定后 ， 留下什 么样的子问题才能保证上述问题的选择是 最优的 4. 证明你的方案是最优的 ， 方法 ： “Cut-and- paste” 清华大学清华大学 软件学院 宋斌恒 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) 2 清华大学清华大学 软件学院 宋斌恒 7 Mathematical model ?Each activity ai has a start time si and finish time fi, where 0≤ si<fi<∞ . ? Compatible【 相容 】 activities: We call two activities are compatible if the two intervals does not overlap (i.e., ai, aj are compatible if si≥ fj or sj≥ fi) ? 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: fi≤ 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！ 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 Aikto Sik and Akj to Skj used within this optimal solution to Sij must be optimal as well. ? Notice! The definition of Aikin 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 Sikcontians more elements than Aik, we could cut out Aik 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 ijjki ij Sjkckic S jic if}1],[],[{max if0 ],[ Converting a dynamic- programming 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 am is used in some maximum-size subset of mutually compatible activities of Sij ?The subproblem Sim is empty 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 bottom- up 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 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￥。