動機
貪心算法並不是僅僅因為每一步的選擇在局部看起來有吸引力就能成功。它們需要一個結構性的理由,說明為甚麼較早的選擇可以被納入某個最優解。擬陣刻劃了這樣一種結構:獨立集對取子集封閉,並且較小的獨立集可以利用較大獨立集中的某個元素進行擴充。這些性質支撐了一類相當廣泛的加權貪心算法的交換證明。
下面的結果求的是最大權基,即極大獨立集。如果權可以為負,那麼這與在任意大小的獨立集中求最大權獨立集是不同的目標。這一區別是定理本身的一部分,而不是實作上的細節。
定義
定義 2.8.1
(擬陣、獨立集與基)
有限擬陣是一個二元組 ,其中 是有限集, 非空,並且滿足:
- 遺傳性質:若 且 ,則 。
- 擴充性質:若 且 ,則存在 使得 。
基是關於包含關係極大的獨立集。反覆擴充可知每個獨立集都可以擴展為一個基,並且任意兩個基的基數相同:否則可以用較大者去擴充較小者。給每個元素賦予一個實數權 。
定義 2.8.2
(按權非遞增順序的貪心掃描)
貪心算法按權非遞增的順序排列元素,權相同時按任意固定的順序處理。它依次掃描這個順序,當且僅當所選集合在加入某元素後仍為獨立集時才加入該元素。即使某些權為負,它也會掃描整個基礎集。
定理
引理 2.8.3
(利用基進行擴展)
若 是一個基, 是獨立集,且 使 為獨立集,則存在 ,使得 是一個基。
定理 2.8.4
(加權擬陣貪心定理)
對於任意有限擬陣和任意實數權函數,貪心算法返回一個最大權基。
證明思路與證明
證明
(以擴充性質把獨立集擴展為基)
為證明擴展引理,從 出發。只要它的大小小於 ,擴充性質就會提供 中的一個元素,可在保持獨立性的前提下加入。當大小達到 時,所得集合包含 、 的全部元素,以及 中除某一個元素 之外的所有元素。它是一個基,並且具有所述的形式。
證明
(最優基包含貪心的各項選擇)
對於貪心定理,最終選出的集合是極大的:某個元素在被掃描時若被拒絕,則在之後選入更多元素也不可能變得可加入,因為獨立集的子集必須是獨立的。因此結果是一個基。我們維護一個包含迄今貪心所作選擇的最優基 。起初任何最優基都可以。假設貪心下一步把 加入先前已選集合 。若 ,則保留 。否則,由引理得到 ,使得 是一個基。
元素 不可能在 之前被掃描:在掃描 的時刻,已選集合是 的子集,而由於 ,加入 後仍會保持獨立。那麼貪心會選中它,這與 矛盾。因此在固定的非遞增順序中 排在 之後,從而 。交換後的基不比最優基輕,因此同樣是最優的;它包含新的貪心集合。由歸納法可知,存在一個包含最終貪心基的最優基,故二者相等。
證明透視
被拒絕元素的論證
交換只依賴一個事實: 是獨立集,從而經由引理得到某個可移除的元素 ,這正是擴充性質被使用的地方。掃描順序隨後給出權的比較。遺傳性質有兩個作用:使拒絕成為永久的,並說明若 在 之前被掃描,那時已選集合包含於 , 本會被接受。論證按貪心所作選擇的個數歸納而告完結:始終保持一個包含迄今所有選擇的最優基,於是最終的貪心基等於某個最優基。權相同並無影響,因為只用到 。若沒有擴充性質,引理便不成立,後面「貪心失效的遺傳族」一節的例子顯示此時貪心會返回非最優的集合。
例題詳解
例題 2.8.5
(基數約束)
設獨立集為 的所有大小至多為二的子集,權分別為 。貪心選取 ,並因容量已滿而拒絕 。所得的基具有最大權七。
例題 2.8.6
(圖擬陣)
對於無向圖,令獨立邊集為森林。貪心按邊權遞減的順序,在不產生圈時加入邊。在連通圖上,其輸出是最大權生成樹,即 Kruskal 最小生成樹算法的最大權對應版本。
例題 2.8.7
(權相同的情形)
若秩為二的擬陣中所有元素的權相等,則不同的固定平局順序可能得到不同的基。每個基都有兩個元素,因此總權相同。該定理允許任意固定的平局順序。
常見錯誤
常見錯誤
(最大權基不等於最優的任意獨立集)
在只有一個元素、秩為一的擬陣中,若權為 ,則唯一的基是權為 的單元素集,而空獨立集的權為零。掃描所有元素解決的是最大權基問題,而不是這個不加限制的獨立集問題。
常見錯誤
(僅有遺傳封閉性並不足夠)
僅有遺傳封閉性不足以推出該定理。擴充性質被用來把貪心選擇擴展為基,並使所有基的大小相同。對於任意的可行集族,證明不能悄悄地假設這一性質。
為甚麼交換引理由擴充性質推出
設 是大小為 的基,包含當前獨立集 ,並設 是獨立集且 。只要當前集合的元素少於 個,擴充公理就可應用於當前集合與獨立集 。它會提供 中一個尚未出現的、可以加入的元素。重複這一過程,直到新的獨立集大小為 。
最終的集合包含 、新元素 ,以及 中恰好 個元素。由於 有 個元素,恰有一個被遺漏。把該元素記為 ,便得到 。它是獨立的,且大小為共同的基大小 ,所以是一個基。這一證明反覆使用擴充性質;「交換」這個名稱是一個結論,而不是未經解釋就假設的額外公理。
貪心證明所維護的是包含迄今所作選擇的最優基,而不一定始終是原來的那個最優基。需要交換時,見證用的最優基可能會改變。新的基不比原來的輕,而它的權又不可能超過原最優基的權,所以其權等於最優值。這就是算法在作出一連串局部選擇的同時,如何在每一步都保有全局最優性證明的原因。
貪心失效的遺傳族
反例模式
有遺傳性而無擴充性
斷言:對任何遺傳族及任意實數權,降序貪心都返回最大權基。設 ,獨立集為 的所有子集與 的所有子集。這個集族具有遺傳性質,但對 與 擴充性質不成立: 和 都不能加入 。取權 、,按降序的貪心選取 ,且無法再加入其他任一元素,得到權三。而獨立集 的權為四。該集族不是擬陣,所以定理不適用。修正之道是要求擴充性質:這個性質正好排除了此集族,而有了它,貪心就是最優的。
這個例子中還有大小不同的極大獨立集,分別為一和二。在擬陣中這不可能發生:若某個極大獨立集比另一個獨立集小,則擴充性質會與它的極大性矛盾。基的大小相等是公理的推論,而不是額外隱藏的假設。
為甚麼森林構成擬陣
對於有限無向圖,取 為其邊集,並稱不含圈的邊集為獨立集。從森林中刪除邊不會產生圈,所以遺傳性質成立。對於擴充性質,設森林 滿足 。若 中沒有任何一條邊連接森林 的不同連通分支,則 的每條邊都落在這些分支之一的內部。在有 個頂點的分支中,無圈圖至多有 條邊。對各分支求和將得到 ,矛盾。因此 中有某條邊連接 的不同分支,並且可以加入而不產生圈。
在連通圖中,每個極大森林都是生成樹。因此,把最大權基定理應用於圖擬陣,便證明了權遞減版本的 Kruskal 算法。將順序反轉,或等價地把權取負,就得到最小生成樹版本。該定理涵蓋權相同的情形,因為證明的每一步都不需要嚴格的權不等式。
基與任意獨立集
當所有權均非負時,最大權獨立集可以在不減少權的前提下擴展為基。因此最大權基在所有獨立集中也是最優的。當權可以為負時,擴展可能使權變差,正如單元素例子所示。掃描全部元素的算法刻意返回一個基,必要時會為了達到基而包含負權元素。
若要在任意實數權下使獨立集的權最大,則在考慮時捨棄所有負權元素,並對正權元素構成的限制運行同樣的貪心規則。每個獨立集都可以捨去其負權元素而不減少其權;權為零的元素也可以省略而不改變其權。正權元素上的限制仍是擬陣,並且該限制中的最優正獨立集可以擴展為該限制的一個基,同時權增加或保持不變。因此貪心定理證明了所得到的正權元素集對於不加限制的獨立集目標是最優的。這是一個相關的推論,並不是掃描全部元素的基算法的目標。
概念視角結構
貪心所得的基是每個權重閾值的基
對實數 ,令 。貪心在掃描任何其他元素之前先掃描完 ,所以輸出與 的交集是 的一個極大獨立子集,大小為 。反過來,基 的權重最大,當且僅當對每個 都有 :它的權重是 加上各個 乘以相鄰權重之間非負的差距後的總和,而沒有基在任何一層能超過秩。
複雜度與神諭的含義
對 個元素排序需要 次比較。之後,通用算法對每個元素進行一次獨立性查詢。其實際執行時間取決於如何檢驗獨立性以及如何表示已選集合。把一次獨立性查詢視為常數時間的神諭(oracle),給出的是神諭調用次數,而不會自動成為具體實作的時間上界。
對於圖擬陣,可以用不相交集合結構來檢驗一條邊是否連接當前不同的分支;其精確成本取決於所選擇的合併與查找操作。對於基數擬陣,獨立性通過當前集合的大小來檢驗。同一個抽象證明適用於兩者,而它們的實作與複雜度分析各不相同。
要檢驗一個給定的輸出,需驗證其獨立性與極大性,並將其權與另行論證的上界比較。僅有獨立性並不能證明權最大。貪心的交換證明為算法自身的輸出提供最優性保證;大小正確的任意獨立集不一定是最大權的。
追蹤一次圖上的交換
例題 2.8.8
(追蹤四頂點圖上的交換)
考慮四個頂點 ,邊 的權分別為 。降序貪心首先接受 和 。它拒絕 ,因為這三條邊構成圈;接受 ,然後拒絕 。其生成樹的權為 。
為了看出交換證明如何證實這一答案,改為從生成樹 出發,其權為十六。貪心的第一條邊 不在 中。加入它會產生頂點 上的三角形;刪除 便得到包含 的、權為十八的樹。第二條貪心邊 已經在其中。最後,向這棵新樹加入 ;產生的圈包含 ,其權較小,因此可以刪除。最終的樹權為十九。這裏的交換見證是明確的邊,而一般定理則在不假設圖的情形下由擴充性質得到見證。
被拒絕的邊可以比之後被接受的邊權更大: 的權為六,而 的權為四。這並不矛盾。是否接受一條邊取決於之前選出的整個森林,而不只取決於權。具體而言,在 和 之後加入 會違反獨立性,而 連接了兩個分支。
貪心不再最優,但兩個擬陣的問題仍然可以有效求解。
通往推廣的路徑
若集合須同時在兩個擬陣中獨立呢?
貪心不再最優,但兩個擬陣的問題仍然可以有效求解。
二分圖匹配就是兩個劃分擬陣的公共獨立集:每個左頂點至多一條邊,每個右頂點至多一條邊。設邊 權重為 ,邊 、 權重為 :貪心取 後即停在 ,而另外兩條邊合起來是 。對兩個擬陣,求最大公共獨立集已有多項式時間算法;對三個擬陣,問題則是 NP 困難的。
總結
擴充性質使得獨立的貪心選擇可以替換最優基中的一個元素。掃描順序保證替換後不會更輕。重複這樣的交換,便對任意實數權給出最大權基。
練習
快速檢查
(在四個元素、權為 的秩為二的基數擬陣中,列出兩種可能的貪心輸出及它們共同的權。)
按掃描順序處理元素,並在每一步後檢查秩。
解答 · 答案
貪心必須取權為六的元素。權同為四的兩個元素中任意一個都可以接著被取,由此得到兩個不同的基,權均為 。秩已滿之後,負權元素不能被包含。
快速檢查
(在四頂點圖擬陣的例子中,從樹 出發。加入 ,並指出可以刪除哪條邊,使得到的樹同時包含 和 。比較新舊權。)
在樹中加入一條邊,恰好產生一個圈。
解答 · 答案
加入 產生圈 。刪除 得到 。原來的權為 ,新的權為 。未改變的邊 仍然連接著頂點 。
快速檢查
(某個遺傳族的獨立集恰為 的所有子集與 的所有子集。給出一個擴充失敗的例子,並選取正權使得降序貪心不是最優的。)
尋找一個獨立集,使較大獨立集中的任何元素都不能加入其中。
解答 · 答案
取 與 ; 中的兩個元素都不能加入 。令 的權為 , 的權各為 。貪心得到 ,但 的權為 。
快速檢查
(在元素權為 的秩為二的基數擬陣中,分別給出最大權基與最大權獨立集。解釋兩個目標為何不同。)
基必須是極大的;獨立集則可以更早停止。
解答 · 答案
最重的基包含權 與 ,總權為 。最優獨立集是權為 的單元素集。基必須是極大的,因此有兩個元素,而任意獨立集可以更早停止。