7 贪心.ppt

7.2 任务选择问题 假定有一系列任务的集合S = {a1, a2, ..., an}，这些任务竞争同一资源，这个资源一次只能被一个任务占用。任务ai占用该资源后，不能中断，直至完成。每个任务ai有一个起始时间si和一个完成时间fi ，且0≤si fi ∞ 。如果任务被选择占用资源，则该任务可在半开时间区间[si,fi)内占用资源。如果任务ai的活动区间[si,fi).和任务aj 的活动区间[sj , fj)互不重叠，则称任务ai和aj是相互兼容的，即他们占用资源时，互不冲突。 任务选择(Task Select)问题就是在任务占用资源互不冲突的条件下，选择尽可能多的任务占用资源，即要选择相互兼容任务的最大子集。 任务安排问题 每一个任务需要使用同一资源 S = {a1, . . . , an} – 任务集合 ai 需要占用资源时间： [si , fi) si = 开始时间 and fi = 结束时间 0 ? si fi ? 任务 ai 和aj 是可相容的如果时间段 [si , fi) 和 [sj, fj) 没有重合 任务安排问题 选取最大的可相容的子集 例如： 最优子结构 定义子问题区间: Sij = { ak ? S : fi ≤ sk fk ≤ sj } 任务必须在ai结束后开始并且在aj开始前结束 任务和 Sij中的任务相容 所有的任务都在fi前结束 所有的任务都 sj 后开始 描述问题 增加假想任务 a0 = [-?, 0) an+1 = [?, “? + 1”) Sij 的范围0 ? i, j ? n + 1 我们假设在Sij中任务已经按结束时间顺序升序排序: f0 ? f1 ? f2 ? … ? fn fn+1 如果 i ≥ j ? 对于一个任务 ak ? Sij: fi ? sk fk ? sj fj 与 fi ? fj矛盾! ? Sij = ? (必须为空!) 我们只需要考虑 Sij：0 ? i j ? n + 1 最优子问题 子问题: 从Sij中选取一个最大可相容子集 假设对于上述子问题的一个解中包含 ak (Sij 非空) Sij的解= (Sik的解) ? {ak} ? (Skj的解) ?Sij的解?= ?Sik的解?+ 1 + ?Skj的解? 最优子问题 Aij 是 Sij 的最优解 要求: Aik 和 Akj 必须是最优解 假设存在 ? Aik’ 包含更多的任务 Size[Aij’] = Size[Aik’] + 1 + Size[Akj] Size[Aij] ? 矛盾: 我们曾经假设 Aij 是 Sij 的最优解 递归解法 任意问题的最优解包含它的子问题的最优解 c[i, j] = Sij的最大可相容子集的大小 如果Sij = ? ? c[i, j] = 0 (i ≥ j) 递归解 如果 Sij ? ? 并且如果我们假设 ak 在一个最优解中 （Sij的最大可相容子集） c[i, j] = c[i,k] + c[k, j] + 1 递归解 k有j-i-1种可能 k = i+1, …, j – 1 ak 不能是 ai 或者 aj (从Sij的定义 ) Sij = { ak ? S : fi ≤ sk fk ≤ sj } 我们检查各种可能的情况并选求最好的 我们可以写出一个动态规划算法 定理 定理7.2设 Sij ? ? 并且am 是Sij中最早完成的任务 : fm = min { fk: ak ? Sij } 有: am 是的最大可相容子集中的一个 Sij的最大可相容子集中的一个 存在一些包含 am的最优解 Sim = ?, 所以选择 am Smj是唯一的非空子问题 证明 假设 ? ak ? Sim fi ? sk fk ? sm fm ? fk fm 矛盾 ! am 并不是最早完成的 ? 没有 ak ? Sim ? Sim = ? Proof Sij的最优解中的一个包含am Aij = Sij的最优解 将任务按完成时间升序排序 让 ak 成为 Aij = {ak, …}的第一个值 如果 ak = am 完成! 否则 换成 am (建立一个新子集 Aij’) 由于 fm ? fk Aij’ 中的任务继续可相容 Aij’和 Aij 的大小一样? am 是在某些最大可相容子集里 这个定理为什么有用 做贪心选择 (最先完成时间的选择) 减少子问题和选择的数量 由自顶向下的顺序解决每个子问题 贪心途径 选择一个最大可相容子集: 选择 am ? Sij am是最先完成的(贪心选择) 将 am 加入最优解的集合 在Smj中解决同样的问题 我