擬陣理論主要是研究定義在一個集合的子集合上的抽象相關關系。不是相關的子集通常也叫獨立集。一個擬陣可以有許多不同但是等價的方法定義。

擬陣與子集系統

定義：

　　子集系統是一個二元組M=(S,L)，它須滿足以下條件：

S是一個有限集(finite setorground set)。
L是由S的一些子集組成的有限非空集。
遺傳性：對任意B∈L，任意A?B，有A∈L（?必須是L的元素）
擬陣是一個子集系統，必須滿足：交換性：對任意A∈L，B∈L，|A|＜|B|，存在一個x∈B-A，使A∪{x}∈L。

　　擬陣是一種組合結構，遺傳性和交換性是擬陣最根本的兩條性質，擬陣上的其他性質都是基于這兩個性質發展出來的。

擬陣上的最優化問題

　　一旦發現了最優化問題的擬陣結構，就可以對該問題實施貪心算法，這是由擬陣的性質決定的。當然仍有大量可以用貪心算法解決的問題無法被擬陣結構覆蓋（如哈夫曼問題，最多不沖突區間問題等）。

　　對于擬陣M=(S,L)，我們對S的每個元素x賦予一個正整數權值w(x)，S的任意子集U的權值w(U)=Σ_x∈Uw(x)，即為其所有元素的權值和。對于M，我們希望求出它的一個權值最大獨立集。

　　貪心算法主要采用局部最優的解決問題的策略，但是在很多時候都不能達到全局最優的效果，那么什么時候使用貪心算法能夠得到全局最優呢？就此引出擬陣的概念。

閉包

　　設M(S,l)是個擬陣，X?S是個子集。對任意的e∈S，若r_M(X∪e)=r_M(X)，則稱e依賴于X，并記e~_MX。當無需強調M時，記e~X。全體S中依賴于X的元素構成的子集稱為X在M中的閉包(closure)，記作

cl_M(X)={e∈S:r(X)=r(X∪e)}

若子集X滿足X=cl_M(X)，則稱X是M的閉集(closed set)。當無需強調擬陣M是，可用cl(X)來代替cl_M(X)。

　　由于X的閉包cl_M(X)是唯一地由X所確定的，因此可以把取閉包的運算看作是一個算子cl_M:2^S→2^S（稱為閉包算子(closure operator)）。

極小圈公理

　　設M(S,l)是一個擬陣。若子集X∈Opp(l)=2^S-l，則X稱為M的一個相關集(dependent set)。極小的相關集叫做極小圈(circuit)。令c(M)表示由擬陣M的全體極小圈組成的集合，則有c(M)=Min(Opp(l))。當C∈c(M)，并且|C|=k時，稱C為M的一個k-極小圈(k-circuit)，k為C的長度。

　　設M(S,l)是一個擬陣，c=c(M)，則c滿足下列性質：

(C1)??c。(因為M(S,l)是擬陣，l滿足獨立集公理，?∈l，故??c)
(C2)若C₁,C₂∈c且C₁?C₂，則C₁=C₂。(若C₁,C₂∈c且C₁?C_2，因為C₁∈2^S-l而C₂是2^S-l中的極小元，所以一定有C₁=C₂)
(C3)若C₁≠C₂，C₁,C₂∈c并且e∈C₁∩C₂，則恒有C₃∈c滿足C₃?(C₁∪C₂)-e。(只要證明C₁∪C₂-e∈2^S-l)

證明C₁∪C₂-e∈2^S-l

秩函數

貪心算法的一般步驟

確定待解問題的最優子結構
設計遞歸求解方式
證明在遞歸的任一階段，最優選擇之一總是貪心的（那么貪心選擇是最適合的）
證明通過做貪心選擇，所有的子問題都為空（除一個以外）
設計實現貪心策略的遞歸算法
將設計好的遞歸算法轉換成迭代算法

貪心選擇　　

　　貪心算法中，我們所做的總是當前看似最佳的選擇，然后在解決經過貪心選擇之后所出現的子問題。其作出的當前的選擇可能要依賴于已經做出的所有選擇，但不依賴于未做出的選擇或子問題的解。貪心算法采取的貪婪策略往往是自頂向下的。核心所在就是要證明每一步所做的貪心選擇最終能產生一個全局最優解。

最優子結構

　　對于一個問題，如果它的一個最優解包含了其子問題的最優解，則稱該問題具有最優子結構（最優子結構的證明采用部分替換法）。

設計貪心算法的一般步驟

將優化問題轉化為：先做出選擇，再解決剩下的一個子問題
證明原問題總是有一個最優解是做貪心選擇而得到的，從而證明貪心選擇的安全性與魯棒性
說明做出貪心選擇之后，剩余的子問題具有一個性質：如果將子問題的最優解和所做的貪心選擇聯合，可以得到原問題的一個最優解

擬陣來源

　　1935年，Whitney把以上兩條性質進行了抽象推廣，提出了擬陣的概念。

擬陣

　　擬陣理論是組合優化的一個分支。擬陣理論并不是因為貪心算法而引入，但是卻是貪心算法的強力輔助。擬陣理論不能完全覆蓋所有的貪心算法（如赫夫曼編碼問題），但它可以覆蓋大多數具有實際意義的情況。

　　在問題模型滿足擬陣結構的情況下，貪心策略總是能夠得到最優解。

擬陣的概念

定義1：子集系統的優化問題

　　

定義2：擬陣

注意：上圖中l∈2S應為l∈2^S，且集合l中的元素稱為擬陣M的獨立集，因此上圖中的1，2，3稱為獨立集公理。擬陣M通常也記作M=(S,l)，以強調這是一個在S上以l中的元素為獨立集的擬陣。

同構

對于給定的兩個擬陣M₁(S₁,l₁)和M₂(S₂,l₂)，若映射?(不是空集，用紅色與空集區分)：S₁→S₂滿足以下條件：

?：S₁→S₂是一個一一對應，
對任意子集X?S₁，X∈l₁當且僅當?(X)∈l₂.

則稱?：S₁→S₂為從M₁到M₂的一個同構。若這樣的?存在，稱M₁與M₂同構，記作M₁≌M₂。對每個擬陣M，易見全體從M到M的同構在映射的復合下構成一個群Aut(M)（稱為M的自同構群）。

貪心算法

定義4：擬陣的權函數

定義5：擬陣的最大權獨立集問題

擬陣的性質

定義3：獨立子集

極大獨立子集與極大線性無關組的關系？？？

定理1

定理2

定理3

貪心算法

擬陣外史

加權擬陣與貪心

一個有限擬陣是一個滿足下列條件的二元組M=(S,I)：

S是一個有限集
I是由S的一些子集組成的有限非空集合（非空族），這些子集稱為S的獨立子集。屬于I的子集要滿足的條件是：如果B∈I且A?B，那么有A∈I。這種性質稱為遺傳性（如果I滿足這種性質我們稱I是遺傳的）。規定，?∈I
若A∈I，B∈I且|B|＞|A|，那么?x∈B-A使得A∪{x}∈I。這種性質稱為交換性質（稱M滿足交換性質）

擬陣例子

　　M=(S,I)是一個擬陣，其中：

　　S={1,2,3}，I={size≤2的子集}={?,{1},{2},{3},{1,2},{1,3},{2,3}}

　　如果說擬陣中的一個獨立子集A不存在擴展，那么就稱它是最大的，這里有一個比較重要的性質：擬陣中所有的最大獨立子集都具有相同的大小

加權擬陣

　　如果一個擬陣M=(S,I)關聯了一個權重函數w，這個函數為S中的每一個元素x賦予一個嚴格大于0的權重w(x)，那么我們稱這個擬陣M是加權的。子集A的權值就是

問題

　　在加權擬陣中尋找最大權重獨立子集，即給定一個加權擬陣M=(S,I)，尋找獨立集A∈I使得w(A)最大

貪心法求解

將S中的元素按照w降序排列
現在有一個集合A（初始的時候為?），按照上面排好的順序依次考慮S中的每個元素，如果說這個元素x滿足A∪{x}是獨立的，那么將x加入A中
A就是答案

擬陣的貪心選擇性

　　假定M=(S,T)是一個加權擬陣，加權函數為w，且S已經按照權重單調遞減排序。令x是S中第一個滿足{x}獨立的元素（存在的話qwq），如果存在這樣的{x}，那么存在S的一個最優子集A包含x

如果一個元素在初始的時候不是最優的選擇，那么隨后也不會被選入最優集合中

1、對于擬陣M=(S,I)，如果x是S中的一個元素，而且是S的某個獨立子集A的一個擴展，那么x也是?的一個擴展

　　證明：由于x是A的一個擴展，說明A∪{x}是獨立的，由于I是遺傳的，所以{x}必然是獨立的，所以是??的一個擴展

2、對于擬陣M=(S,I)，如果x是S中的一個元素，且不是?的一個擴展，那么它也不是S中任何獨立子集AA的擴展

　　證明：（就是1的逆否命題）

?　　所以我們可以得知，如果一個元素首次不能用于構造獨立集，之后永遠也不可能用到了

　　因此尋找起始元素時，貪心地直接跳過S中那些不是?的擴展的元素不會導致錯誤的結果，因為這些元素永遠都不會被用到

擬陣具有最優子結構性質

次模函數

參考文獻

賴虹建. 擬陣論[M]. 高等教育出版社, 2002.

次模函數

擬陣

總結

以上是生活随笔為你收集整理的贪心算法及其理论依据——拟阵的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。