最优解型构、子问题、最优子结构特性 .i1234 67891011 3 6 88212 09 10 11121416 非平凡最优解中一定包含一个活动ak:So,12问题从ak处被分解为两 个子问题，如何建模这两个子问题？ 假设k为4：a1,a2,a3构成第一个子问题？a5,a6,..,a11构成第二个子问题？ 简单的子问题建模，将一 无法阐明问题的最优子 结构特性！ Si:the set of activities that start after activity a finishes and that finish before activity a starts
最优解型构、子问题、最优子结构特性 S0,12： Sij: the set of activities that start after activity ai finishes and that finish before activity ajstarts. 非平凡最优解中一定包含一个活动ak：Sij/0,12问题从ak处被分解为两 个子问题，如何建模这两个子问题？ 假设k为4：a1,a2,a3构成第一个子问题？a5,a6,…,a11构成第二个子问题？ 简单的子问题建模，将 无法阐明问题的最优子 结构特性！
最优解型构、子问题、最优子结构特性 23 567 8 9 10 一个样本输入： Si 3 5 8 8 f 9910 1. 1214 S:the set of activities that start after activity afinishes and that finish before activity a starts. Ai:maximum set of mutually compatible activities in S Ao,12:ta a4 as/9;a11 is a solution of So.12
最优解型构、子问题、最优子结构特性 一个样本输入： Sij: the set of activities that start after activity ai finishes and that finish before activity ajstarts. Aij: maximum set of mutually compatible activities in Sij A0,12: {a1 ; a4 ; a8/9; a11} is a solution of S0,12
非平凡最优解中一定包含一个活动ak:Sjj问题被分解为Sk和 Sk两个子问题 If we denote the size of an optimal solution for the set Si;by c[i,j],then we would have the recurrence g]=ci,个+ck+1. S,中最多相互兼容的活动数 我们知道其中包含某活动ak c,={ if Sij=0 max {c[i,k]+c[k,j]+1 if Si 这里的k怎么表达？
Sij中最多相互兼容的活动数 我们知道其中包含某活动ak 这里的k怎么表达？ 非平凡最优解中一定包含一个活动ak：Sij问题被分解为Sik和 Skj两个子问题
动态规划解法 在上述递归关系中，4，可以是S中任一活动，每选定一个特 定的α，则确定特定的子问题。动态规划方法按照合适的次序 解所有的子问题。 问题3：是否有可能不必解所有的子问题？ 0 是否一定要解当k为6时的 8 8 12 11 14 S0.6和S6,12两个子问题
动态规划解法 在上述递归关系中，ak可以是Sij中任一活动，每选定一个特 定的ak , 则确定特定的子问题。动态规划方法按照合适的次序 解所有的子问题。 是否一定要解当k为6时的 S0,6和S6,12两个子问题
问题4： 所谓“GREEDY”是指什么？