有些貪心證明依賴可行集的結構,而非區間或圖的特定圖像。擬陣刻畫了其中一種結構。我們會證明最大權定理,並看清楚目標改變時為何負權需要小心處理。
獨立性與增廣
定義 6.1.1
(擬陣、獨立集與基)
有限擬陣由有限地集 及非空集合族 構成,滿足兩項條件。
- 遺傳性:若 且 ,則 。
- 增廣性:若 且 ,則存在 使 。
的成員稱為獨立集;基是包含關係下極大的獨立集。由非空及遺傳性,空集獨立。
這些是關於包含關係的結論,與權重無關。
引理 6.1.2
(基的大小相同,獨立集可擴展為基)
在有限擬陣中,任何兩個基含有相同數目的元素,而且每個獨立集都包含於某個基之中。
證明
(增廣性對抗極大性)
設 為基且 。由增廣性,存在 使 獨立,這與 的極大性矛盾。因此 ,由對稱性得兩者大小相等。
設 為獨立集。若 不是極大的,便存在獨立的真超集,以它取代 。每次取代都使大小增加,而大小不超過 ,所以經有限步後 成為極大,即成為包含原來集合的基。
按遞減權重貪心選取
給每個元素 一個實數權重 ,並記 。按權重非遞增排序所有元素,得 ,滿足 ,以任何固定規則打破平手。由 開始依次掃描;恰在加入後仍獨立時加入該元素。即使權重為負也要掃描。記 為前 個元素的前綴, 為從中已選出的元素。
定理 6.1.3
(貪心法返回最大權基)
對任意實數權重,掃描所得的集合 是一個基,而且對每個基 都有 。
證明
(先證極大性,再作前綴比較)
是基。 獨立,因為它由空集開始,而元素只在保持獨立時加入。設 。掃描到 時,當時的集合 滿足 。因 ,若 獨立,則由遺傳性 也獨立。所以不能再向 加入任何元素, 是極大的。
每個前綴都處理得最優。同一論證表明 在 中極大獨立:此前被拒的 內元素,不能在 增長後變得可行。若有獨立集 滿足 ,增廣性給出 使 獨立,與極大性矛盾。所以 在 的獨立子集中大小最大。
與基比較。令 為任意基,其元素按排序為 ,即 ,。由引理, 亦有 個元素 (按排序),。集合 由遺傳性是獨立的,所以 。因此 的第 個所選元素不遲於位置 出現:。由於次序為權重不增,每個 都有 。對 求和,得 。平手、負權及 (此時兩個和皆為零)都包括在內。
證明透視
各項假設在何處使用
證明在不同地方分別用到兩條公理。遺傳性出現兩次:一次用來說明被拒元素在 增長後仍然被拒,一次用來說明 的前 個元素構成某個前綴的獨立子集。增廣性恰好出現一次,把「在 中極大」提升為「在 中大小最大」。等大小引理本身是增廣性的推論,它使 與 的兩個和含有相同數目的項。
不明顯的一步是逐個前綴比較,而不是把兩個集合直接比較。不等式 把關於權重的陳述變成關於獨立集的計數陳述,排序次序再把「不遲於出現」換成「權重至少一樣大」。論證逐項收結: 對 都滿足 ,所以兩個和可以比較。
要留意的是證明從未用到權重的正負號,只用到排序次序,這就是負權對基沒有影響的原因。真正使論證失效的是公理不成立,下面的遺傳性例子便是如此。
因此,對任意實數權重,貪心法返回最大權基;最優解未必唯一。直接實作的排序需要 次比較,另有 次獨立性測試;每次測試成本取決於擬陣的表示。
快速檢查
(貪心基定理可否使用負權?)
留意證明用到權重的哪一種性質。
解答 · 答案
可以。它仍在所有基中最大化,因為證明比較的是等長的已排序權重表,只用到權重的次序,沒有用到正負號。
例題
例題 6.1.4
(分割擬陣)
假設 有兩個紅元素 ,權重為 ,以及兩個藍元素 ,權重為 。集合獨立當且僅當紅、藍各至多一個。遺傳性顯然成立。對增廣性,若 , 必用到 沒用的某種顏色; 中該顏色的元素可增廣 。貪心法依次掃描 ,選出 ,總權重 ;餘下元素會重複顏色。這是最大權基,在此例中也是最大權獨立集。
例題 6.1.5
(平手與負權)
令 ,所有至多含兩個元素的集合皆獨立。遺傳性明顯;若 ,任取 ,大小仍至多為 。取 、,並以 先於 打破平手。貪心法接受 ,再接受 ( 有兩個元素),然後拒絕 。輸出 的權重為 。
對照所有基,即三個二元素集合:,,。最大值為 ,出現兩次。若以相反方式打破平手,則返回 ,是另一個權重相同的集合。
例題 6.1.6
(環元素永不被選取)
令 ,獨立集只有 和 ;元素 是環,因為 不獨立。遺傳性成立;增廣性成立,因為唯一滿足 的組合是 、,而 可增廣。設 、。貪心法先掃描 ,因 不獨立而拒絕;然後接受 。輸出 的權重為 ,它是唯一的基,所以即使存在較重的元素它仍是最優。若 也是環,唯一的基便是 ,此時 ,權重為 。
反例模式
基未必是最佳獨立集
取單元素地集 , 與 均獨立,且 。唯一的基是 ,故貪心法返回權重 ;但在所有獨立集中,空集權重為 。若權重全非負,每個獨立集均可擴展為基而不減少權重;此時最大權基也是最大權獨立集。權重可正可負時,兩個目標不同。
常見錯誤
常見錯誤
(略過負權元素)
權重轉為負數後便停止掃描,是常見的想法。對基的問題這是錯的。在 、 的例子中,若在 之前停止,返回 :它獨立但不是基,因為仍可加入 。定理針對的是基,所以每個元素都必須掃描。在所有獨立集中求最大權是另一個問題。
常見錯誤
(以為最優解唯一)
定理給出的是最優權重,不是唯一的最優集合。在上面的例子中, 與 的權重都是 ,輸出取決於打破平手的規則。任何規則都可行,但返回的集合並非唯一。
僅有遺傳性並不足夠
遺傳性可以在局部檢查,於是人們可能期望貪心法對每個具遺傳性的系統都最優。證明所需要的正是增廣性;欠缺它,結論不成立。
反例模式
具遺傳性但不是擬陣的系統
令 ,獨立集為 的所有子集,以及 的所有子集。此系統有遺傳性但不是擬陣: 與 違反增廣性。若 、,遞減貪心法選 後不能選餘下元素,總權重為 ; 的權重為 。局部可行性測試本身不是全局最優證明。
習題
快速檢查
(在分割例中,若藍色權重 改為 ,結果如何?)
先把四個元素重新排序。
解答 · 答案
排序變為 。貪心法選該藍元素與 ,總權重為 ; 與 會重複顏色。
快速檢查
(為何前綴中被拒的元素不能在以後變得可行?)
對較早的已選集使用遺傳性。
解答 · 答案
若它和較大的已選集可行,遺傳性便使它和此前的子集可行,但當時它正是在那個子集上被拒的。
快速檢查
(單元素負權例中的最大權獨立集是甚麼?)
比較 與 。
解答 · 答案
,權重為 ,因為 的權重為 。