次序令依賴關係安全
令 為以鄰接表表示的有限有向無環圖(DAG)。為清楚起見,假設沒有平行邊;一條路徑由其有序頂點序列指定。選定容許的起點集合 。每個 到自身的零邊路徑算作一條路徑。我們會數出由任一容許起點到各頂點的路徑,並在邊帶實數權重時求最大路徑權重。不可達頂點的路徑數為零,沒有有限的最大值。
拓撲排序一節已證明,在 DAG 的任何拓撲次序中,每條邊都由較早頂點指向較後頂點。這正是動態規劃所需的條件:處理某個頂點時,其所有前驅到達的路徑已經作出貢獻。不同合法次序的中間表未必相同,但最終答案相同。
定義 5.5.1
(由容許起點出發的路徑數與最大路徑權重)
令 為滿足下列條件的路徑 的集合:,每個 都是邊,,。路徑數為 。最大路徑權重 是 中 的最大值,其中零邊路徑的權重為 ;若 為空,則 ,。
可供觀察的次序
對邊 、、,起初入度為零的頂點是 和 。先後移除 的兩種次序均可;移除兩者後,可再移除 ,然後是 。若邊為 、、,且 孤立,移除 和 後剩下環 ,沒有零入度頂點。
在元件的第一個情況,先選 再選 ,或復原後先選 再選 。顯示次序雖然不同,兩者都把 放在兩個前驅之後。元件顯示移除次序及剩餘入度;它不計算路徑數或邊權。下面會自行計算。第二個情況則顯示剩餘有向環如何令 DAG 前提失效。上一段在靜態閱讀或匯出時提供相同的必要狀態。
按最後一條邊數路徑
初始化:當 時令 ,否則令 。按拓撲次序處理頂點;處理 時,對每條出邊 執行
定理 5.5.2
(按最後一邊計數)
當 時令 ,否則令 ,並按拓撲次序用上述更新式處理 DAG 的頂點。則對每個頂點 都有 ,而且 在 被處理之後不再改變。
證明
(按拓撲次序歸納)
為何計數正確?每條以 結尾的非空路徑都有唯一最後一邊 ;刪去該邊後得到一條以 結尾的路徑。反過來,加上該邊便得到一條以 結尾的路徑。不同類別的最後一邊不同,因此互不重疊。當 ,初始的 貢獻一條零邊路徑。即使另一個容許起點有路徑通往某個起點,這些貢獻也會額外加入其零邊路徑。按拓撲次序歸納,處理 之前,所需貢獻已全部且只有它們到達。
證明透視
無環性、零邊路徑與簡單邊用在哪裏
關鍵的一步是最後一邊分解:它把長度不受限的路徑集合換成以 的入邊為指標的不相交聯集,所以每條邊只需作一次加法。拓撲次序使歸納有根據:每條邊 的 都排在 之前,所以處理 時每個入鄰居都已推送其最終計數,之後不可能再有東西加到 。無環性保證這樣的次序存在,同時使 為有限集, 才是一個數。沒有平行邊也在同一步用到:若有兩條 ,同一個頂點序列就會對應兩次加法,與「路徑就是其頂點序列」的約定不符。初始值 對應唯一沒有最後一邊的路徑;它是被加上去而不是被取代,因為屬於 的頂點也可以是較長路徑的終點。論證在處理完最後一個頂點時收尾,此時以任何頂點結尾的每條路徑都已恰好記在某一條最後一邊上。
最大權重,包括負邊
給每條邊有限實數權重 。對 初始化 ,其餘頂點取 。按拓撲次序,對每條滿足 的邊 執行
定理 5.5.3
(按最後一邊求最大權重)
對 令 ,其餘頂點令 ,並按拓撲次序用上述更新式處理 DAG 的頂點,跳過起點滿足 的邊。則對任意有限實數權重,每個頂點 都有 。
證明
(對最大權重作同樣的歸納)
同樣以最後一邊歸納可證: 是由容許起點到 的路徑之最大總權重;若沒有路徑,則保留 。對容許起點,零邊路徑權重為零,但進入該點的路徑可以改善它。有限 DAG 的路徑只有有限多條,因此可達時最大值存在。負權重不會造成困難,因為拓撲次序先處理每個前驅,且沒有有向環;這不是 Dijkstra 算法。
例題 5.5.4
(第一幅圖上的計數與權重)
對元件的第一幅圖,取 ,權重 、、。兩種顯示次序都給出以下最終值:
| 頂點 | ||||
|---|---|---|---|---|
| 1 | 1 | 2 | 2 | |
| 0 | 0 | 2 | 5 |
由容許起點到 有兩條路徑: 及 。再加上 得到兩條到 的路徑;權重最大的由 出發,權重為 。 及 的計數來自零邊路徑。元件不顯示此權重/計數表;它顯示計算所使用的次序。
例題 5.5.5
(有路徑通往的容許起點)
取 ,邊 權重為 、 權重為 ,拓撲次序為 。對 ,初始 、。沿 處理 :,。沿 處理 :,。到 的路徑是零邊路徑 和路徑 ,所以 ;零邊路徑的權重為 ,勝過權重為 的 。到 的路徑是 (權重 )和 (權重 ),所以 ,。這就是容許起點在自己的零邊路徑之外還收到其他貢獻的情形。
例題 5.5.6
(四個頂點上的完全前向 DAG)
取頂點 ,所有 的邊 權重為 ,,按 的次序處理。則 、、、,內部頂點集 的每個子集對應一條路徑。權重方面,、、、:最長路徑是 ,有三條邊,雖然共有四條路徑。當 ,同一公式給出 ,即一條單邊。
概念視角代數
把計數看成三角線性方程組
設 為鄰接矩陣,邊 對應 ;設 為行向量, 時 ,否則為 。按最後一條邊計數,就是 ,即 。在拓撲次序下 是嚴格上三角矩陣,所以 是對角線全為 的三角矩陣,而更新規則恰是前向代入:每個 都由較早的項決定。等價地,,這是有限和,因為 達到頂點數時 。對上面的四個頂點,得 。
常見錯誤
(把每個頂點的計數都從一開始)
只有容許起點才有零邊路徑。取 與唯一的邊 ,若令每個頂點 ,就會得到 ,但由 到 的唯一路徑是 。只應在 時令 。
常見錯誤
(把每個最大權重都從零開始)
把非起點初始化為 會掩蓋負權重。取 與權重為 的邊 ,真值是 ,但更新式 返回 ,沒有任何路徑達到這個權重。同樣的初始化還會使不可達頂點看似可達,權重為 。非起點應取 ,並跳過起點值為 的邊。
實作與限制
先求拓撲次序,並檢查它是否包含全部 個頂點。否則應報告 DAG 方法不適用,不能把部分次序當成完整答案。
反例模式
含有向環的圖上的遞推式
斷言:即使圖中有有向環,只要按某個固定次序處理頂點,計數遞推式同樣有效。取 ,邊 、、,次序為 。初始 ,。處理 使 加 ;處理 使 加 ;處理 使 加 。最終表為 、、。這張表無論怎樣解讀都不對:從 出發的簡單路徑有三條,即 、、,計數應為 ;若改數途徑,則到 與到 都有無窮多條(、,等等)。 處的 包含途徑 ,但它的貢獻從未傳給 。任何次序都會剩下這樣一條向後的邊,因為有向環沒有最早的頂點。完整的拓撲次序恰在圖無環時存在,所以檢查次序是否包含全部 個頂點是方法的前提,而不是形式。
然後初始化陣列,並掃描每個出邊鄰接表一次。這使用 次算術操作,圖本身以外需要 個陣列儲存項;其位元空間亦會隨所編碼的數值增長。若需要實際最大權重路徑,當最大值改善時儲存前驅;若多條路徑同樣最優,應指定平手處理方式。
操作次數假設對路徑數的算術為常數時間。精確計數可能很大:對頂點 、包含所有 的邊 的簡單 DAG,當 ,由 到 有 條路徑,每個內部頂點子集對應一條。因此精確整數需要愈來愈多位元。模數計數回答的是另一個問題;固定字長溢出可能破壞精確結果。
習題
快速檢查
(令 ,邊為權重 的 、權重 的 、權重 的 ; 為孤立點。給出四個頂點的 和 。)
解答 · 答案
計數為 、、、。最大權重為 、、、。經 的路徑權重為 ,勝過權重為零的直接邊。
快速檢查
(為何把每個容許起點初始化為計數一,不代表其計數必然保持為一?)
解答 · 答案
初始值數的是零邊路徑;動態規劃之後可加入由另一個起點進入該頂點的路徑。
快速檢查
(若 Kahn 次序不完整而仍有頂點,為何算法必須拒絕把它當作答案?)
解答 · 答案
部分次序沒有處理所有頂點,餘下依賴及輸出尚未計算。對 Kahn 算法而言,剩餘圖含有向環;有限 DAG 的證明不適用。