第16章_贪心算法.ppt

16.4.2 加权胚上的贪心算法 Greedy算法返回1个最优子集 A是独立子集易从Φ独立开始用归纳法证明 Lemma16.7 （胚呈现贪心选择性质） 设M=(S,I)是加权胚，权函数为w，且S已按权值的单调递减有序，设x是S的第一个使{x}独立的元素（若这样的x存在）。若x存在，则存在S的一个最优子集A包含x。（即说明第一步贪心选择正确） * 16.4.2 加权胚上的贪心算法 * * 16.4.2 加权胚上的贪心算法 下面的引理和推论说明：若一元素开始未被选中，则此后亦不可能被选中 Lemma16.8 设M=(S,I)是任一胚，若S的一个元素x是S的某个独立子集A的一个扩张，则x亦是Φ的一个扩张 * 16.4.2 加权胚上的贪心算法 推论16.9 设M=(S,I)是任一胚，若S的一个元素x不是Φ的扩张，则x也不是S的任何独立子集A的一个扩张 pf：由引理16.8易证 该推论告诉我们，若一开始某元素没被选中，此后亦不会选中，保证Greedy算法开始的正确性 * 16.4.2 加权胚上的贪心算法 引理16.10（胚具有最优子结构性质） 对于加权胚M=(S,I)，设x是Greedy算法选中的第一个元素，找一个包含x的权最大的独立子集的剩余问题可归结为找加权胚M’=(S’,I’)的一个权值最大的独立子集，这里： 且M’的权函数是M的权函数，但只限于S’。我们称M’是由元素x引起的M的收缩，它是M的子问题。 * * 16.4.2 加权胚上的贪心算法 Th16.11 （胚的贪心算法的正确性） 若M=(S,I)是权函数为w的加权胚，则调用Greedy(M,w)将返回一个最优子集 pf: ①由推论16.9知，一开始被忽略的元素可以放弃，因为它们不是Φ的扩张意味着此后也不会是任何独立子集的扩张。 ②一旦一个元素x被选中，引理16.7保证了算法将其扩充到A中是正确的，因为存在一个最优子集包含x。 * 16.4.2 加权胚上的贪心算法 ③引理16.10蕴含着剩余子问题是在M’中找一最优子集。在Greedy将A置为{x}之后，剩下的各步骤可解释为是在胚M’中进行的，因为?B∈I’，B在M’中独立等价于B∪{x}在M中独立。因此，Greedy的后续操作将找出M’的一个最优子集（可用归纳法），Greedy的全部操作可以找到M的最优子集 若一应用问题能抽象为加权胚，则一定能用贪心法求出其最优解 * 16.5 一个任务调度问题 问题描述 在单处理器上对单位时间任务进行最优调度 输入 任务集：S={a1,a2,…,an}，每个任务在单位时间内完成，总时间为n 截止期：?ai∈S，ai的截止期di为整数，且1≤di≤n，即ai须在di或di时刻之前完成 权（罚款）：?ai∈S，ai的权wi≥0，表示ai没有在di或di之前完成所导致的罚款，但提前完成或按时完成的任务没有罚款 输出：求出S的一个调度，使总罚款最小 显然S的任意枚举都是一个调度方案，在总时间n内肯定完成，但我们力图使延期完成的任务权值和最小 * 16.5 一个任务调度问题 将问题抽象为加权胚 早任务：在给定的调度中，能按期或提前完成的任务（即在deadline之前完成任务） 迟任务：在给定的调度中，在截止期之后完成的任务 早任务优先形式：将早任务排在迟任务之前的调度 任何调度均可安排成早任务优先形式 例：……aj……aj…… → ……ai……aj…… 迟 早 早 迟 交换位置不影响ai和aj的早迟特性，即总罚款不变 * 16.5 一个任务调度问题 调度的规范形式 早任务在前、迟任务在后（即先将其按早任务优先形式调度）；并且将所有早任务按deadline单调增次序调度（迟任务可按任意次序调度）。 规范形式的调度不改变任务的早迟特性，因此任何调度均可安排成该形式而保持总罚款不变 例： * 16.5 一个任务调度问题 这里s≥1。在规范形势下，ai应和aj交换： 1.aj交换后，其完成时间由k+s提前至k，仍是早任务 2.交换前aj是早任务，即k+s≤dj，由djdi知k+sdi，故ai交换到k+s时刻完成，它仍是早任务 * 任务顺序 早任务 迟任务 原调度次序 …ai…aj… … 完成时刻 …k…k+s… … deadlines didj … 16.5 一个任务调度问题 最优调度的规范次序 因为任一调度都有一规范形式，所以最优调度也存在规范形式 在最优调度S中找出早任务集A 将A中任务按deadlines递增序排列 迟任务集S-A可按任意序排列 注意： 因为早