算法設計技巧既是組織計算的方式,也是組織證明的方式。貪心算法需要一個理由,說明某個局部選擇可以被永久確定下來。分治法需要互相獨立的較小子問題,以及正確的合併步驟。動態規劃需要子問題的值保留後續決策所需的全部資訊。掌握這些證明責任,比死記一串算法名稱更有用。
動機
假設一間房間同一時間只能舉辦一項活動。每項活動都有開始時間和結束時間。如果所有活動價值相同,選擇結束得早的活動看來是明智的,因為這樣為將來留下了更多可用時間。然而,如果活動的價值各不相同,一項短小而價值低的活動可能會擋住一項價值高得多的活動。輸入對象幾乎沒有變化,但目標函數的改變足以令貪心證明失效。
帶權排程將引出動態規劃。按結束時間對活動排序後,會出現一個有用的邊界:選定某項活動之後,所有與之相容的較早活動都位於排序列表的某個特定前綴之中。因此,一個子問題可以用一個前綴下標來概括。如果不能識別出這種充分的狀態,「試試動態規劃」就只是一句口號。
排序本身提供了分治法的例子。我們可以分別對兩半獨立排序,再合併兩個已排序的輸出。證明的核心並不在於每次遞歸調用的規模都較小,那只能說明算法會終止。正確性還需要一個合併不變式,說明每一個被選出的下一個元素確實是全序中的下一個元素。
定義
定義 3.1.1
(活動、相容與兩種目標)
活動 佔用一個左閉右開區間 ,其中 。一項活動恰好在另一項活動開始時結束是容許的。兩項活動的區間不重疊時,稱它們相容。無權排程問題要最大化所選活動的個數;帶權版本則給每項活動指定非負整數權重 ,並最大化所選活動的權重之和。空選擇總是可行的。
定義 3.1.2
(前驅下標與前綴最優值)
將活動排序,使 ,結束時間相同時按任意固定規則決定先後。對於帶權排程,定義 為滿足 的最大下標 ,若不存在這樣的下標則取零。由於 ,每一項與 相容的較早活動都屬於以 結尾的前綴。令 為僅使用活動 時所能得到的最大權重,並規定 。
定義 3.1.3
(最優子結構)
如果在固定了外圍的選擇之後,較大問題的最優解使用了相關較小問題的最優解,就稱該問題具有最優子結構。這一性質需要證明:若較小問題的解並非最優,將其替換後必須仍保持可行性,並使整體目標值得到改善。
定義 3.1.4
(比較排序與操作計數)
比較排序算法只透過比較輸入的鍵來得知順序。對於下面的下界,鍵兩兩不同,且所有排列都可能出現。對於所述的上界,一次比較或一次基本算術運算算作一次操作。當數值變大或輸入座標的編碼很長時,位元複雜度可能還需要額外的因子。
定理/命題
定理 3.1.5
(最早結束時間對無權排程是最優的)
在與已作選擇相容的活動中,反覆選取結束時間最早的活動。所得的相容集合具有最大基數。本定理針對無權目標,以及長度嚴格為正的左閉右開區間。
定理 3.1.6
(帶權排程的遞歸式)
對 ,
在排序並求出所有前驅下標之後,該表可按下標遞增的順序計算,並且可以沿著取得最大值的選擇重建出一個最優集合。
兩者的分別在於承諾。貪心算法永久地選定第一項活動,因為交換論證證明了存在一個最優解包含這一選擇。動態規劃則同時保留「包含」與「不包含」兩種可能,直到比較過它們各自可達到的最優值。它並不明確列舉每一種選擇,因為許多選擇所需要的是同一個較小前綴的最優值。
命題 3.1.7
(合併排序正確,且使用 次比較)
合併排序回傳輸入的一個有序重排,對 個鍵共進行 次比較。陣列實作使用 的額外儲存空間。
定理 3.1.8
(比較排序需要 次比較)
任何在 個互不相同的鍵的所有排列上都正確的確定性比較排序算法,在某個輸入上至少作 次比較,而 。
證明思路或證明
證明
(交換最優解的第一項活動)
設 是全局結束時間最早的活動,並取一個按時間順序排列的無權最優排程。若它非空,記其第一項活動為 ,並將 替換為 。由於 ,所有後續活動(其開始時間至少為 )仍與 相容。因為 是第一項,所以沒有需要照顧的更早活動。該替換保持所選活動的個數不變。因此存在一個以 開頭的最優解。其餘活動必須在 或之後開始,對這個較小的問題可遞歸地應用同樣的論證。每次選擇至少移除一項活動,所以該過程終止並得到最優解。空實例是顯然的。
證明透視
交換論證在哪裏用到各項假設
關鍵一步是從任意一個最優解出發,只改動它的第一項活動。這樣做是合法的,原因有三。由於 的結束時間不遲於任何活動,所以 ,最優解的每一項後續活動都在 或之後開始,因此也在 或之後開始。這裏左閉右開區間很重要:一項活動恰好在另一項活動結束時開始,仍然相容。區間長度嚴格為正,使「按時間順序的第一項」有明確意義。
目標函數只在一處出現:替換是一項換一項,所以個數不變。對帶權問題,替換還需要 ,而沒有任何條件保證這一點。論證對活動個數作歸納而完結:選定 之後,剩下的問題由在 或之後開始的活動組成,活動個數較少,在其中求得的最優解與 合併,就是整個實例的最優解。
證明
(包含或不包含最後一項活動)
對於帶權排程,按是否包含 來劃分前綴 中的可行排程。不包含 的排程,其最大值為 。包含 的排程只能含有在 之前結束的較早活動,這些活動都位於前綴 之中。它們其餘的選擇可以被替換為該前綴的一個最優解,而不會產生重疊。因此其最大值為 ,且兩個候選值都是可行的。取二者的最大值即證明了等式。由於 ,按下標遞增的順序求值時只會用到已經算出的值。
證明
(重建沿著取得最大值的分支進行)
重建時,從 開始。若不包含分支取得 ,則移至 。否則包含 ,並移至 。出現平手時可以任選一邊,只要所選分支取得最優值即可。下標嚴格遞減,所以該過程終止。遞歸式保證累計所選的權重等於原問題的最優值,而且每次包含操作都移到一個相容的前綴。這就證明了輸出的集合本身(而不僅僅是它的目標值)是正確的。
證明透視
為甚麼小的狀態就足夠
前綴下標之所以有效,是因為選擇活動 只透過一個結束時間的邊界來限制較早的選擇。我們不需要記住被拒絕活動的整個歷史。在另一個具有多個資源或額外依賴關係的排程問題中,前綴下標可能丟掉關鍵資訊。只有在證明了狀態描述了所有剩餘約束之後,遞歸式才算得到論證。
證明
(合併保持有序前綴,逐層計算成本)
對於合併排序,把列表分成長度幾乎相等的兩部分,遞歸地對它們排序,然後合併。合併期間保持如下不變式:輸出是有序的,並且由已從兩個有序輸入中取出的最小元素組成。當前較小的隊首元素不大於任一輸入中的任何剩餘元素,把它附加到輸出中即保持該不變式。一旦某個輸入耗盡,另一個輸入的其餘部分可按原順序直接附加。每個元素恰好被取出一次,因此合併的成本是線性的。對列表長度作歸納即證明排序的正確性,而遞歸輸入逐步變小則證明終止性。
在遞歸的每一層,各子列表的長度之和至多為 ,而在到達單元素葉子之前,樹的高度至多為 。每層的合併工作是線性的,因此對 共需 次操作。這種按層計算的論證無需假定輸入長度恰好是 2 的冪。使用輔助陣列的實作需要 的額外儲存空間;而不必要地複製數據的樸素實作,其常數與儲存行為可能有所不同。
證明
(計算判定樹的葉子)
比較模型的下界解釋了這一成本為何重要。互不相同的鍵共有 種可能的順序。確定性的二叉比較判定樹至少有 個葉子,所以某條路徑的長度至少為 。對 ,階乘中至少有 個因子不小於 ,從而當 增大時得到 的界。這是比較排序的最壞情況下界,並不適用於利用額外資訊(例如位數有界的整數數位)的算法。
例題詳解
例題 3.1.9
(同一輸入,兩種目標的計算)
取活動 、、、、,權重分別為 。按結束時間的順序恰好就是上面列出的順序,前驅下標為 。帶權表為 ,隨後依次是 。回溯選出 ,然後是 ,再是 ,總權重為十七。最早結束的貪心算法在這裏也選出 ,但它們在這個例子上一致,並不能證明貪心算法能解決帶權問題。
反例模式
權重不同時,最早結束的貪心會失敗
人們可能預期,一條對活動個數已證明為最優的規則,對最大化權重也依然最優。取兩項重疊的活動: 權重為一, 權重為一百。最早結束的貪心算法取 ,它與另一項衝突,所以其值為一;而單獨一項 是可行的,其值為一百。表格的結果一致:前驅下標為 ,所以 ,。無權情形的交換證明在替換第一項活動時仍能保持個數,但無法保持總權重。證明責任的失敗恰好指明了究竟是哪一條定理不再適用。修正的方法就是遞歸式,它比較兩個分支,而不是提早承諾。
例題 3.1.10
(帶有明確平手約定的合併)
合併有序列表 與 。每次取較小的隊首元素,並在相等時選擇左邊的隊首,得到 。如果鍵帶有原始位置,則在鍵相等時選左半部分,可以保持它們跨越兩半的原有順序,因此合併排序可以是穩定的。穩定性是有序性之外的附加性質,應當從平手約定出發加以證明,而不能僅憑「合併」一詞推斷。
例題 3.1.11
(表中的平手與重建)
取 權重五, 權重五, 權重十。按結束時間排序, 與 的平手以把 排在前面來決定,活動依次為 。前驅下標為 ;,因為 ;,因為 。於是
在 時兩個分支打成平手,重建時可以任選一邊。取不包含分支,移至 ;那裏不包含分支只得 ,所以包含 ,並移至 ,再包含 :所選集合是權重十的 。若在 取包含分支,則選出同樣權重為十的 。兩個輸出都是最優的; 與 在邊界點 相接而不重疊,這正是左閉右開約定的作用。
排序需要 次比較,而對已排序的結束時間進行二分搜尋,可在 次比較內求出所有 。隨後動態規劃表與重建共使用 次算術運算和 個儲存項。若每個權重至多有 位元,則每個表項的值至多是最大權重的 倍,至多需要 位元。在位元模型下,算術階段並非常數成本。端點比較的成本同樣取決於時間的表示方式;關於操作次數的陳述不應隱藏這一選擇。
常見錯誤
常見錯誤
(最優子結構不等於貪心證明)
最優子結構本身並不能證明某個貪心規則有效。動態規劃可以利用最優子結構,同時保留多個可能的第一選擇。貪心算法對其特定的永久性決策,需要更強的交換論證或「保持領先」論證。
常見錯誤
(遺漏了約束的狀態)
不要用遺漏了某項約束的狀態來做記憶化。例如,如果遞歸式只按剩餘活動的個數編號,就往往會因為忘記已經施加的結束時間邊界而失敗。活動個數相同的兩個子問題,可行的排程可能不同。
常見錯誤
(遞歸式還不是高效的算法)
遞歸式的存在也不能保證實作是高效的。直接遞歸地計算帶權排程,可能會多次重複訪問同樣的前綴。用表格則每個狀態只計算一次。反過來,一個遞歸式未經證明的大表格,可能高效地算出錯誤的答案。
總結
交換論證為安全的貪心承諾提供依據。分治法把輸入分成互相獨立的較小部分,並證明合併步驟。動態規劃確定充分的子問題狀態,透過窮盡各種情形證明遞歸式,並避免重複計算。正確性、重建、終止性與成本模型,是算法說明中彼此有別的不同部分。
練習
練習 3.1.12
(證明:先選最短的區間,不一定能使相容活動的個數最大。)
基礎
解答(3)
- 1
選取區間
取 、 和 ,長度分別為 、 和 。
- 2
執行最短優先規則
最短的區間是 。它與 相交於 ,與 相交於 ,所以選了它之後,沒有其他活動相容。該規則只選出一項活動。
- 3
與最優解比較
區間 與 相容,因為前者恰好在後者開始時結束。可以選出兩項活動,所以最短優先並非最優。持續時間短與結束時間早確實是不同的貪心規則;最早結束的規則會先選 ,再選 。
練習 3.1.13
(對區間 、、,權重為 ,計算帶權表,並給出一個最優集合。)
核心
解答(3)
- 1
求前驅下標
結束時間已按 排好。。對 , 而 ,所以 。對 ,, 而 ,所以 。
- 2
按下標遞增填表
關鍵一步
- 3
重建一個最優集合
在 時,不包含分支取得 ,所以移至 。那裏不包含分支只得 ,所以包含 ,並移至 。最優集合是 ,權重為 。兩側的區間雖然相容,但總權重只有八,所以最大化個數解決的是另一個目標。
練習 3.1.14
(對於面額為一、三、四的硬幣,證明在金額為六時,反覆取盡可能大的硬幣會失敗。並給出求最少硬幣數的正確遞歸式。)
核心
解答(4)
- 1
執行貪心規則
貪心先取 ,再取 ,再取 ,共三枚硬幣。但 只用兩枚,所以對金額六,貪心並非最優。
- 2
寫出遞歸式
關鍵一步
依據: 每個非空的解都有最後一枚硬幣,刪去它就得到較小金額的一個解。
- 3
在較小的金額上檢驗遞歸式
,,,,,,與 相符。
- 4
論證正確性
刪去最優解的最後一枚硬幣 ,得到 的一個解,它本身必須是最優的,否則替換它就能改進整體。反過來,把 附加到 的最優解上是可行的。面額為正,使每次引用的金額都更小;面額一的存在則保證每個金額都能湊出。
快速檢查
(解釋為甚麼排序的下界與對 中整數的計數排序並不矛盾。)
想想計數排序除了比較之外還用了甚麼資訊。
解答 · 答案
計數排序利用整數的取值去索引計數,並利用了有界的鍵域。它所用的資訊並非僅僅透過輸入鍵之間的二叉比較獲得,因此比較判定樹的假設並不適用。其成本包括鍵域的大小,通常為 ,當 很大時這個成本可能很大。