擬陣理論第9講擬陣理論

擬陣理論擬陣（matroid）關于貪心算法的一種優(yōu)美的理論用于判斷一個問題能否應用貪心策略求解可涵蓋很多貪心法求解的問題但不是所有的貪心算法都符合擬陣理論擬陣的定義稱一個有序對M

=(S,?)為擬陣，如果有窮：S是一個有窮集合遺傳（獨立）：?為S的一個非空獨立子集的集合，滿足如稱?的這種性質為遺傳性。果B∈?且A?B，那么A∈?。顯然空集?∈?3)交換：如果A∈?，B∈?，且|A|<|B|，則存在某個元素x∈B-A使得A∪{x}∈?。 稱M滿

換性?！皵M陣”這個詞由HasslerWhiteney最早開始使用的，他曾研究矩陣擬陣。其中S的元素是一個給定矩陣的各個行，如果某些行線性無關，則它們是獨立的，以所有獨立行集合構成?，可以證明M=(S,?)是擬陣。定義在無向圖上的一個擬陣對一個無向圖G=(V,E)，定義有序對MG=(SG,?G)如下：集合SG定義為E，即圖G的邊集。如果A是E的子集，則A∈?G當且僅當A中無回路。即一組邊A是獨立的，當且僅當子圖GA=(V,A)是一個森林。定理16.5

對于無向圖G=(V,E)，MG=(SG,?G)是擬陣。證明：顯然，SG=E是有窮集合；并且，?G是遺傳的，因為森林的子集還是森林。現(xiàn)在，只需要證明MG滿 換性。設GA=(V,

A)和GB=(V,B)都是森林，且|A|<|B|。也就是說，B比A有 的邊。定義在無向圖上的一個擬陣一個有k條邊的森林恰好有|V|-k棵數(shù)。因為每增加一條邊能且只能把森林中的兩棵樹 一棵樹。于是森林GA中有|V|-|A|棵樹，森林GB中有|V|-|B|棵樹?？梢娚諫B中的樹比森林GA中少，因此森林GB中存在一棵樹T，T的頂點屬于森林GA中的兩棵不同的樹。而樹T顯然是連通圖，因此T中存在一條邊(u,v)，使得結點u,v分別屬于森林GA中的兩棵不同的樹。把邊(u,v)加入到森林GA，不會產(chǎn)生環(huán)，即A+{(u,v)}∈?G即MG滿 換性。由此根據(jù)擬陣的定義，MG=(SG,?G)是擬陣。■最大獨立子集擴張：對于擬陣M=(S,?)，集合A∈?，元素x

A，如果能保證把x加入到A中并保持A的獨立性，即A∪{x}∈?，則稱x是A的一個擴張。例如，對于圖的擬陣MG

，如果A是一個獨立的邊集，則邊

e是A的一個擴張，當且僅當e不在A中，且將e加入到A中后不產(chǎn)生環(huán)。最大獨立子集：如果A是擬陣M的一個獨立子集，且它沒有任何擴張，則稱A是最大獨立子集。也就是說，A不被M中更大的獨立子集所包含。最大獨立子集定理的證明定理16.6

擬陣中所有最大的獨立子集的大小都相同。證明：反證法。設A是擬陣M的一個最大獨立子集，假設存在M的另一個更大的獨立子集B，則根據(jù)交換性，A可以擴張到一個更大的獨立子集A∪{x}∈?，x∈B-A。這與A是M的最大獨立子集。證畢?！隼鐚τ趫DG的擬陣MG，MG的每個最大獨立子集都是一棵包含|V|-1條邊且恰好連接了G中的所有頂點的的樹。其實這就是一棵G的生成樹。擬陣擬陣M

=

(S,

?)是

的，如果有 函數(shù)w，w(x)

→R+，x∈S函數(shù)w對與子集A?S有和式w(A)=∑

x∈Aw(x)對于某個A∈?，如果w(A)最大，稱A為擬陣M的最優(yōu)子集最優(yōu)子集一定是最大獨立子集（因為w(x)>0，x∈S

）最小生成樹到擬陣最優(yōu)子集問題的設w(e)，e∈E是圖G=(V,E)上邊的長度函數(shù)，定義擬陣

MG上的權函數(shù)w’(e)=w0-w(e)，其中w0>max{w(e),e∈E}。則最小生成樹T=(V,A)對應于最優(yōu)子集A。擬陣上的貪心算法GREEDY(M,

w)A

←?對S[M]按權函數(shù)w降序排列for

eachx

∈S[M]，按w(x)單調(diào)降序依次取出45f

A

∪

{x}

∈?[M]then

A←

A

∪

{x}6

return

A其中S[M]和?[M]表示M的組成，w表示權函數(shù)算法的執(zhí)行時間分析，步驟2排序為Θ(nlgn)，步驟3~5對每個x做一次，設檢驗A∪{x}獨立性需要f(n)時間，則

GREEDY算法的執(zhí)行時間為Θ(nlgn+nf(n))擬陣具有貪心選擇性質引理16.7

具有

函數(shù)w的

擬陣M

=

(S,

?)，設S按權值的單調(diào)遞減順序排序。設x是S中第一個使{x}獨立的元素。如果x存在，則存在一個包含x的最優(yōu)獨立子集A證明：如果這樣的x不存在，則唯一的獨立集合為空集，證明結束。否則，設B為任意非空最優(yōu)子集，并假設x

B（否則，讓A=B，證明結束）。可以證明，B中不存在權值大于w(x)的元素，對任意y∈B

，有w(x)≥w(y)。根據(jù)交換性，

從{x}開始，通過B一步一步構造最大獨立子集A，最終A=B-{y}+{x}，其中y∈B

，于是w(A)

=w(B)-w(y)+w(x)

≥w(B)，故A是包含x的最優(yōu)獨立子集。

■貪心選擇的過程不會遺漏引理16.8

對擬陣M

=(S,?)，對于任意的x∈S，如果x是S的獨立子集A的一個擴張，則x也是?的一個擴張。證明：如果x是獨立子集A的一個擴張，則A∪{x}是獨立的，根據(jù)遺傳性，{x}也是獨立的，所以x也是?的一個擴張■推論16.9

對擬陣M=(S,?)，如果某個x∈S不是?的一個擴張，則x也不會是S的任意獨立子集A的一個擴張。這個結論告訴

，在擬陣中的貪心選擇過程，在一開始選擇時丟棄的元素，在后面的選擇過程中也不再會用到。擬陣具有最優(yōu)子結構的性質引理16.10

對 擬陣M=(S,?)，設x∈S為在GREEDY算法中第一個選擇的元素，則找一個包含x的最優(yōu)子集問題可以歸約為找出 擬陣M

'=

(S',?')的最優(yōu)子集問題，這里S'={y∈S:{x,y}∈?}，?'={B?S-{x}:B∪{x}∈?}，其中M'的權函數(shù)為（受限于S'）M的權函數(shù)（稱M'為M由x引起的收縮）證明：如果A是包含x的M的獨立子集，那么A'=A-{x}

就是M'的一個獨立子集。反之，由M'的獨立子集A'可得M的一個獨立子集A=A'

∪{x}。而兩種情形中都有w(A)=w(A')+w(x)，因此由M中包含x的一個最大權值解可以得M'中的一個最大權值解，反之亦然。■擬陣上貪心算法的正確性定理16.7

GREEDY(M,w)返回M=(S,?)一個最優(yōu)子集。證明：分析算法的整個過程：根據(jù)推論16.9，一開始被略去的那些不是?的擴張的元素可以不考慮；一旦選擇了第一個元素x，由引理16.7可知，將x加入A是正確的，因為存在包含x的最優(yōu)子集。最后，由引理16.10，隱含著余下的問題就是一個在M的由

x引起的收縮M'中尋找一個最優(yōu)子集的問題（B在M'中獨立等價于B∪{x}在M中獨立，其中B∈?'），剩余步驟可找出M'中一個最優(yōu)子集。整個步驟的結果就是M的最優(yōu)子集?！鰯M陣證明練習證明：(S,?k)是擬陣，其中S為任意有窮集合，?k為S的所有階最多為k的子集構成的集合，k

≤|S|。證明：關于矩陣T的(S,?)是擬陣，其中S為T的所有的列構成的集合，且A∈?當且僅當A中的各列是線性無關的。練習題解問題1的證明：S本身就是有窮集合；對于任意B∈?k和任意A?B，都有|A|≤|B|≤k，所以A∈?k，滿足遺傳性；又對于任意的A,B∈?k且|A|<|B|，任取x∈B-A，則|A∪{x}|=|A|+1≤|B|≤k，所以A∪{x}∈?k

，滿 換性。故(S,?k)是擬陣。■練習題解問題2的證明：S本身就是有窮集合；對于任意A∈?，A中各列線性無關，則A的任意子集中的各列也線性無關，所以滿足遺傳性；對于階更大的獨立子集B，假設B中的任意一列都和A中的列線性相關，因為|A|<|B|，可以得出B中的各列線性相關，這與B是獨立子集

；故必定存在x∈B-A，x與A中的各列和在一起仍線性無關，即A∪{x}∈?，故滿

換性。于是(S,?)是擬陣?！鲆粋€任務調(diào)度問題——擬陣的應用一個任務調(diào)度問題在單處理器上對若干單位時間任務進行最優(yōu)調(diào)度，其中每個任務都有一個截止時間和超時懲罰。包含n個單位時間任務的集合S={a1,a2,...,an}n個整數(shù)值的期限d1,d2,...,dn，每個di滿足1≤di

≤n且任務ai要求在di前完成n個非負的權（或懲罰）w1,w2,...,wn，如果任務ai沒有在時間di前結束，則導致懲罰wi，而如果任務在期限之前完成，則沒有懲罰。問題：找出S的一個調(diào)度，使之最優(yōu)化因延期調(diào)度而導致的總懲罰。早任務優(yōu)先對于一個給定的調(diào)度，一個任務在調(diào)度中遲了，如果它在規(guī)定期限之后完成；否則這個任務在調(diào)度中是早的。任何一個調(diào)度總可以安排成早任務優(yōu)先的形式，即早任務總是安排在遲任務之前。因為：對處于遲任務aj后的早任務ai

，交換ai

和aj不影響ai是早的和aj是遲的。早任務優(yōu)先調(diào)度的規(guī)范形式：早任務先于遲任務，且按期限的遞增序對早任務進行調(diào)度。對某調(diào)度，首先將其安排成按早任務優(yōu)先的形式，然后只要有兩個分別完成于時間k和k+1的早任務ai

和aj使得dj

<di

，則交換ai

和aj。容易看出，交換后aj顯然仍是早的，因為

提前了aj。而對于ai

，因為k

+1≤dj

（因為交換前aj是早的），于是k

+1<di

，所以交換后ai

也是早的。歸約為早任務集合問題根據(jù)早任務優(yōu)先調(diào)度的規(guī)范形式，尋找最優(yōu)化調(diào)度問題可歸約為尋找最優(yōu)調(diào)度中早任務構成的集合A的問題。一旦A確定，可按期限單調(diào)遞增的順序列出A中的所有任務，然后按任意順序輸出遲任務(S-A)，就可產(chǎn)生出最優(yōu)調(diào)度的一個規(guī)范形式。如果存在關于A中任務的一個調(diào)度，使得A中的任務都不遲，稱一個任務集合A是獨立的。某一個調(diào)度中的早任務集合就構成了一個獨立的任務集。設?是所有獨立的任務集構成的集合。如何判斷任務集A是否是獨立的？設Nt(A)表示A中期限為t或更早的任務的個數(shù)（t早任務個數(shù)），t=0,1,...,n，其中N0(A)=0。關于任務集A是否獨立的引理引理16.12

對于任意的任務集合A，下列命題等價：1)集合A是獨立的；2)對于t

=0,1,...,n，有Nt(A)≤t；3)如果對A的任務按期限的單調(diào)遞增的順序進行調(diào)度，則沒有一個任務是遲的。證明：假設存在t使得Nt(A)>t

，則不存在A的無遲任務的調(diào)度，因為有多于t個任務要在時間t之前完成，與A獨立

，故1到2成立。2到3是顯然的，因為按期限單調(diào)遞增進行調(diào)度不可能出現(xiàn)遲任務。最后，3到1可根據(jù)獨立任務集的定義直接得出。■最小化遲任務的懲罰之和等價于最大化早任務懲罰之和只要找出一個擬陣，即可按 擬陣的貪心算法解此問題單位時間調(diào)度問題的擬陣定理16.13

如果S是一個帶期限的單位時間任務的集合，且?為所有獨立的任務集構成的集合，則(S,?)是擬陣。證明：一個獨立的任務集的每個子集肯定是獨立的。為證明交換性，設B和A為獨立任務集，且|B|>|A|，設k為使Nt(B)≤Nt(A)成立的最大的t