【正文】 證 .設(shè) S第一個元素 x滿足 {x}?I. 若存在優(yōu)化子集 A包含 x， 則引理得證 . 否則 , 設(shè) B是任意非空優(yōu)化子集 , x?B. 顯然 , ?y?B， W(x)?W(y). 如下構(gòu)造含 x的優(yōu)化子集 A: 初始 : A={x}?I。 用交換性 : ?y?BA, 若 A?{y}?I, A=A?{y}, 直至 ?A?=?B?. 顯然， ?z?B, A=(B{z})?{x}. 于是 , W(A)=W(B)W(y)+W(x)?W(B). 因為 B是優(yōu)化子集 , 所以 W(A)?W(B), W(A)=W(B). A是優(yōu)化子集 , 且 x?A. HIT CSamp。E 引理 M=(S, I)是一個 Matroid. 如果 x?S不是空集 ?的 extension, 則 x不是任何獨立子集的 extension. 證 .反證 .設(shè) x?S是獨立子集 A的 extension但不是 ?的 extension. 由于 x是 A的 extension, A?{x}?I. 由 M的遺傳性 ， {x}?I, 即 {x}是 ?的 extension, 矛盾 . 推論 , 則永遠不會被選中 . 推論 素而產(chǎn)生錯誤 . HIT CSamp。E ?優(yōu)化子結(jié)構(gòu) 引理 x是第一個被 Greedy算法選中的元素 . 包含 x的優(yōu)化子集 A包含子問題 M’=(S’, I’)的優(yōu)化 子集 A’=A{x}, M’=(S’, I’)定義如下 : S’={y?S?{x, y}?I}, I’={B?S{x}?B?{x}?I} 而且 M’的權(quán)函數(shù)與 M的權(quán)函數(shù)相同 . 證 .若 A是 M的優(yōu)化子集且 x?A, 則 A’=A{x} ?A. 因為 A=A’?{x}?I, 所以 A’=A{x}?I’. 若 A’不是 M’的優(yōu)化子集 , 則存在 M’的一個優(yōu) 化子集 B使得 W(B)W(A’). 由于 B?{x}?I, W(A)=W(A’)+W(x), W(B?{x})=W(B)+W(x)W(A’)+W(x)=W(A), 與 W(A)優(yōu)化矛盾 . HIT CSamp。E ?算法正確性 定理 M=(S, I)是一個 Matroid, W是 M的權(quán)函數(shù) , Greedy(M,W)返回一個 M的優(yōu)化子集 . 證 . ① . 引理 3說明 , 任何沒有被 Greedy選中的 S元素 , 以 后不會被選中 ， 可以不再考慮 . ② . 一旦 S的第一個 x被選中 , x可以加到 A, 因為引理 2說明存在一個包含 x的優(yōu)化子集 . ③ . 引理 4意味著余下的問題是在 M’中求解最優(yōu)子 集的問題 . Greedy算法是按照上述三個規(guī)則工作的 ， 所以 Greedy(M,W)返回一個 M的優(yōu)化子集 . HIT CSamp。E A taskscheduling problem HIT CSamp。E ? 單位時間任務 需要一個單位時間就能夠完成的任務 ? 單位時間任務的調(diào)度問題 輸入： 單位時間任務集 S={1, 2, … , n} 正整數(shù)任務期限 D={d1,d2,… ,dn}, 任務 i須在 di前完成 非負權(quán)集 W={w1,w2,… ,wn}, 任務 i不在 di前完成罰款 wi 輸出： S的一個調(diào)度 (S的一個執(zhí)行順序 ), 具有最小總罰款 問題定義 HIT CSamp。E ? 轉(zhuǎn)換為加權(quán) Matroid的優(yōu)化子集問題 定義 1. 設(shè) S是一個任務調(diào)度 .一個任務在 S中 是遲的 如 果它在規(guī)定的期限之后完成 。 否則 是早的 . 定義 2. 如果在一個調(diào)度中 , 早任務總是先于遲任務 , 則稱該調(diào)度具有 早任務優(yōu)先形式 . 定義 3. 如果一個調(diào)度具有早任務優(yōu)先形式而且按期 限單調(diào)遞增順序執(zhí)行各任務 , 則稱該調(diào)度具有 規(guī)范化形式 . HIT CSamp。E ? 任務調(diào)度的規(guī)范化 第一步 : 將調(diào)度安排成早任務優(yōu)先形式 , 即如果早 任務 x跟在遲任務 y之后 , 交換 x和 y的位置 。 第二步 : 如果任務 i和 j是早任務 , 而且分別完成于時 間 k和 k+1, djdi, 交換 i和 j的位置 . ? 調(diào)度優(yōu)先形式不改變?nèi)魏稳蝿盏脑缁蜻t狀態(tài) ? 調(diào)度規(guī)范形式不改變?nèi)魏稳蝿盏脑缁蜻t狀態(tài) 尋找最優(yōu)調(diào)度問題成為尋找在該最優(yōu)調(diào)度中的早 任務集合 A的問題 . 一旦 A被確定后，就可以按期 限單調(diào)遞增序列出 A中的所有元素 , 然后按任意順 序列出遲任務 (即 SA) HIT CSamp。E 定義 A稱為獨立的如果存在一個關(guān)于 于 A的調(diào)度 , 使得 A中的任務皆非遲任務 . 例 . 一個優(yōu)化調(diào)度的早任務集合是獨立 任務集合 . 以下 : 用 I表示所有獨立任務集合的集族 用 Nt(A)表示 A中期限小于等于 t的任務數(shù) HIT CSamp。E 引理 1. 對于任何任務集合 A, 下邊的命題等價 : 1. A是獨立集合 , 2. 對于 t=1, 2, …, n , Nt(A)?t, 3. 如果按照期限遞增順序調(diào)度 A中任務 , 則 A中無遲任務 . 證 . 1?2. 如果 Nt(A)t, 則有多于 t個任務需要在 t時間 內(nèi)完成 , 不存在使得 A中無遲任務的調(diào)度 . 2?3. 若 A中任務依其期限遞增排列 , 則 2意味著 排序后 , 在 時間 t之前必須完成的 A中任務 數(shù)至多為 t. 于是 , 按 期限遞增順序調(diào)度 A中 任務 , A無遲任務 . 3?1. 顯然 . HIT CSamp。E 定理 1. 若 S是一個帶期限的單位時間任務的集合 , 且 I為 所有獨立任務集構(gòu)成的集族 , 則 M=(S, I)是一個 Matroid. 證明 . 1. S是非空有限集合 . 2. I是 S的子集的非空集族 , 因為單個任務集屬于 I. 3. 遺傳性 : 若 A?I, B?A, 則 B?I. 4. 交換性 : 設(shè) A, B?I, |B|?|A|, k=max1?t?n{t | Nt(B)?Nt(A)}. 于是 , B中包含了比 A中更多的具有期限 k+1的任務 . 設(shè) x?BA, x具有期限 k+1. 令 A’=A?{x}. 往證 A’獨立 . 對于 1?t?k, Nt(A’)=Nt(A)?t, 因為 A是獨立的 . 對于 k?t?n, Nt(A’)?Nt(B)?t, 因為 B是獨立的 . 于是 , A’是獨立的 . k Nj(B)?Nj(A) Nt(B)?Nt(A) HIT CSamp。E 最后 , 任務調(diào)度問題轉(zhuǎn)換為 M=(S, I)上尋找最優(yōu)子集問題， M的加權(quán)函數(shù)為 W(罰款 ) HIT CSamp。E HIT CSamp。E