要求每個地點恰好到訪一次時,通常不能每步只挑最便宜的出邊。這個選擇可能令某個未訪地點再也無法到達,也可能令最後回程昂貴。嘗試所有到訪次序確實能解題,卻重複計算很多子問題:不同前綴可能為未來留下完全相同的選擇。
要運用動態規劃,我們須精確說明哪些前綴可以互換。在這裏,關鍵是已到訪頂點的集合,以及目前終點。前綴內部次序影響已付成本,但不再影響哪些頂點尚可使用,以及下一條邊能從哪裏出發。每個這樣的狀態,只需保留最便宜的前綴。
這是精確方法,時間仍是指數級。它利用頂點數少時的重複狀態,並沒有令任意大型巡迴問題都變得容易。
先定義路線,再定義狀態
頂點為 ,其中 。對不同頂點 ,有向邊 或者存在並帶整數成本 ,或者不存在。成本可以為零或負數。不假設對稱或三角不等式。
從 0 出發的簡單路徑,列出互不相同的頂點,以 0 開始,並在相鄰頂點之間使用存在的邊。當 ,哈密頓(Hamilton)巡迴是這樣一條到訪全部 個頂點的路徑,再接一條存在的邊返回 0。因此 0 在開頭和結尾各出現一次,其他頂點各出現恰好一次。我們要最小化所走 條邊的總成本。固定由 0 出發不會漏掉任何這類環:每個環都可由 0 開始書寫。
當 ,明確採用以下約定:零條邊的巡迴成本為零,路線為 [0]。不要求亦不計算自環,即使矩陣對角項為負也一樣。其他情況的對角項同樣無關,因為路徑內不容許重訪頂點。
定義 14.1.1
(精確已訪集合與終點狀態)
對包含 0 的 及 ,令 為從 0 到 、已訪頂點集合恰好為 的簡單路徑之最小成本。若沒有這樣的路徑,寫成 。
單頂點路徑給出 。凡 而終點為 0 的狀態都不可達:由 0 開始的簡單路徑,不能在內部返回 0。 或 的狀態不合法,也不需要使用。
「恰好」阻止我們把經過額外頂點的便宜路徑,當成那些頂點仍未使用的前綴。終點也不可省略:兩條路徑即使到訪同一集合,仍可能在不同頂點結束,下一條邊的成本或可用性就不同。
移除最後一條邊,推導遞推
定理 14.1.2
(最後一條邊遞推)
設 包含 0,且 、。符合 的路徑,在到達 之前必停於某個 ,並沿存在的邊 到達 ,而且
這裏沒有任何候選時,最小值定為 。
證明
(移除最後一條邊,再把它接回去)
取任何符合 的路徑,移除最後的 。由於列出的頂點互不相同,剩下的路徑恰好到訪 ,並在 結束。其成本至少為 ,故完整路徑的成本不小於某個遞推候選。取最便宜的合資格路徑,可知右方最小值是它的下界。
反過來,取右方任一可達候選,及一條實現該前綴最小值的路徑。頂點 尚未在其已訪集合內,所以接上存在的 ,就形成恰好具有所需已訪集合的簡單路徑,成本等於該候選。因此最便宜候選能實現,給出反方向不等式。若沒有候選,任何合資格路徑都不可能有最後一條邊,狀態便不可達。
證明透視
互不相同與「恰好」在哪裏起作用
兩個不等式都依賴簡單路徑的同一個性質:頂點互不相同。在下界部分,它保證移除最後一條邊後,剩下路徑的已訪集合恰好是 。在上界部分,它提供 不在前綴的已訪集合內,所以接上 得到已訪集合恰好為 的簡單路徑。非常規之處,是兩個不等式用的前綴不同:一個方向取 的最優路徑,另一個方向則對每個候選 分別取最優前綴。證明從未用到成本的正負,只用到成本沿路徑相加。論證以 作歸納收尾:右方每一項都對應少一個頂點的集合,基底是 。若沒有互不相同這個條件,移除最後一條邊後,前綴可能仍含 ,遞推就不再描述已訪集合。
不可達前綴不提供候選,沒有任何候選的最小值定為 。每個依賴的集合都少一個頂點,因此集合大小給出無環的計算次序。
有限圖只有有限多條簡單路徑,所以即使有負成本,每個可達最小值都由某條路徑實現。我們沒有反覆沿環鬆弛:每次轉移都新增一個未訪頂點。因此負環不會令這個有限簡單路線問題的成本無下界。
等價的前向實作,從可達 出發,對任何 且存在 的頂點,用 改善 。這些是同一批轉移,只是說明方向相反。
為何可以丟棄其他前綴
引理 14.1.3
(等價的前綴可以互換)
設兩條從 0 出發的簡單路徑,恰好到訪同一集合 ,並在同一頂點 結束。若由 外的一串頂點,再加上返回 0,能把第一條路徑完成為哈密頓巡迴,則同一串頂點也能完成第二條路徑,而兩條巡迴的成本相差,恰為兩個前綴成本之差。
證明
(後續路線只看集合與終點)
能完成其中一個前綴的後續序列,只能使用 外的頂點,再返回 0。另一前綴有完全相同的未用頂點及下一步出發點 ,故同一後續序列對它也合法,新增成本亦相同。
所以把較貴前綴換成最便宜前綴,既不破壞完成路線,也不會增加總成本。論證不要求邊權非負;它要求後續的可行性與成本只取決於已訪集合、目前終點及未來邊。若另有依賴先前到訪次序的限制,就可能需要更豐富的狀態。
反例模式
到同一終點的最便宜路徑,可能訪錯集合
取三個頂點,邊 成本為 1,、、、 成本都為零。沒有 ,也沒有其他邊。唯一哈密頓巡迴是 ,成本為 1。
但由 0 到終點 1 的最便宜簡單路徑是 ,成本為零。若把它當成只到訪 的前綴使用,就可能產生錯誤的零成本路線 ,重複到訪頂點 2。每個終點只存一個最便宜值會丟失必要資訊;必須分開 與 。
能走完全路徑,不代表能收尾成環
定理 14.1.4
(由全集狀態得出最優巡迴)
設 。哈密頓巡迴存在,當且僅當有某個 使 有限,而且存在邊 。這時最小巡迴成本是
證明
(巡迴就是全集路徑加一條收尾邊)
每條哈密頓巡迴,都是一條從 0 出發、恰好到訪 並在某個 結束的簡單路徑,再接上一條存在的邊 ;反過來,每個這樣的配對都是巡迴。其成本是路徑成本加 。對固定的 ,後一項是常數,所以以 為最後頂點的最便宜巡迴,使用成本為 的路徑。對 取最小值就得到公式;若沒有符合的 ,便沒有巡迴。
有限的 保證有哈密頓路徑,並不保證有巡迴,因為收尾邊可能不存在。若沒有候選,應回報沒有巡迴,而不是傳回任意大的數字。
例題 14.1.5
(加上收尾成本後,才比較完整巡迴)
考慮以下有向成本矩陣;破折號表示缺邊或不使用的對角項:
| 由/至 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | — | 2 | 9 | 8 |
| 1 | 6 | — | 3 | 7 |
| 2 | 4 | 5 | — | -2 |
| 3 | 1 | 6 | 4 | — |
對 ,在 2 結束的路徑是 ,成本為 ;在 1 結束的則是 ,成本為 。再延伸到終點 3,要比較 與 ,所以 。
| 全集終點 | 收尾成本 | 巡迴候選 | |
|---|---|---|---|
| 1 | 13 | 6 | 19 |
| 2 | 13 | 4 | 17 |
| 3 | 3 | 1 | 4 |
最優路線為 ,成本是 。例如成本 13、在 1 結束的全集路徑是 ;它不是成本 13 的巡迴,因為返回 0 還要加 6。
常見錯誤
(只最小化路徑成本,而非巡迴成本)
取邊 、、、 成本都為 , 成本為 , 成本為 。最便宜的全集路徑是 ,成本為 ,但收尾要 ,這條巡迴成本是 。路徑 成本為 ,收尾只要 ,巡迴成本為 。只按 選終點會傳回 ,而不是最優的 ;比較終點之前,必須先加上收尾成本。
編碼集合,而非到訪次序
用整數遮罩表示集合,第 個位元為一,當且僅當 。成員判定用 mask & (1 << i);加入原本不存在的頂點用 mask | (1 << i);全集遮罩為 (1 << n) - 1。位元位置表示頂點名稱,寫出的二進位數字並不記錄到訪次序。
每個前向轉移都把一個零位元設成一,所以新遮罩的數值嚴格大於舊遮罩。因此按遮罩數值遞增迭代,是合法拓撲次序,即使同一集合大小的遮罩不一定連續出現。每個狀態在用來延伸之前,已收到所有可能改善。
當轉移嚴格改善一個狀態,就在該精確狀態的父項表記下前一終點。前一遮罩可由移除新增終點求得。重構時必須同時保留目前遮罩與終點:同一終點在不同子集狀態下,可以有不同前驅。保留任一最小成本前驅便足夠;輸出要求並不是字典序最小巡迴。
可執行實作及其契約
輸入是非空方陣,每項為整數或 None,後者表示邊不存在。整數零是真正的零成本邊。對角項忽略。函數有最優巡迴時傳回 (cost, witness),沒有時傳回 None。多於一個頂點時,路線在結尾重複 0;單頂點約定則傳回 (0, [0])。程式只讀矩陣,不修改它。
def minimum_hamiltonian_tour(weights):
n = len(weights)
if n == 0 or any(len(row) != n for row in weights):
raise ValueError("a nonempty square matrix is required")
if n == 1:
return 0, [0]
limit = 1 << n
dp = [[None] * n for _ in range(limit)]
parent = [[None] * n for _ in range(limit)]
dp[1][0] = 0
for mask in range(1, limit):
if not mask & 1:
continue
for last in range(n):
cost = dp[mask][last]
if cost is None:
continue
for nxt in range(1, n):
if mask & (1 << nxt):
continue
edge = weights[last][nxt]
if edge is None:
continue
new_mask = mask | (1 << nxt)
candidate = cost + edge
old = dp[new_mask][nxt]
if old is None or candidate < old:
dp[new_mask][nxt] = candidate
parent[new_mask][nxt] = last
full = limit - 1
best = None
endpoint = None
for last in range(1, n):
cost = dp[full][last]
closing = weights[last][0]
if cost is None or closing is None:
continue
candidate = cost + closing
if best is None or candidate < best:
best = candidate
endpoint = last
if endpoint is None:
return None
path = []
mask = full
last = endpoint
while mask != 1:
path.append(last)
previous = parent[mask][last]
mask ^= 1 << last
last = previous
path.append(0)
path.reverse()
path.append(0)
return best, path
程式假設項目符合整數或 None 的承諾,並核查矩陣形狀。缺邊以 is None 判斷,因此零及負成本仍然合法。每個遮罩都配置獨立串列。每個已記錄父項,都來自較小遮罩的可達轉移;重構因此每步移除一個已訪非零頂點,最終到達基底狀態。不需要基底狀態的父項。
例題 14.1.6
(父項鏈也記錄前驅用了哪個集合)
對四頂點最優路線,把位元 0 寫在最右方,父項鏈是
重構先反向收集 ,倒轉得到 ,再加上收尾頂點 0,成為 。每次移除位元,都證明一個頂點從已訪集合中恰好移除一次。成本須對照原本的有向邊核查,收尾邊也要計算。
例題 14.1.7
(最小的巡迴:兩個頂點與一個頂點)
取 ,、。程式設 dp[1][0]=0。從遮罩 延伸到頂點 ,得 dp[3][1]=0+5=5、parent[3][1]=0。全集遮罩 只有終點 ,收尾成本為 ,所以 best 。重構先加入 ,移到父項 ,在遮罩 停止;加入 、倒轉、再加上收尾的 ,得到路線 。若邊 不存在,收尾成本是 None,沒有終點合資格,函數傳回 None:全集路徑存在,巡迴卻不存在。當 ,函數不使用對角項,直接傳回 。
常見錯誤
(用真值判斷邊是否缺失)
寫成 if not edge: continue,會把成本 當作缺邊。對兩個頂點,、,邊 會被跳過,找不到巡迴,函數傳回 None,但成本 的巡迴 其實存在。缺邊必須以 is None 判斷,零及負成本才保持合法。
計算狀態數,並守住問題邊界
命題 14.1.8
(子集動態規劃的成本)
對 個頂點,此實作做 次算術運算,儲存 個表格單元,並在 時間內重構路線。
證明
(先數狀態,再數轉移)
共有 個遮罩,每個遮罩有 個終點,所以每張表至多有 個位置,當中包含這個簡單實作配置的非法或不可達位置。每個可達狀態至多考慮 個下一頂點,每次只做常數次操作,得 。對終點取最小值的最後一步花 。重構每步移除一個位元,所以至多 步。
兩張表都是指數大小,所以 只增加一些,也可能令方法無法實用。
這些界把遮罩操作及整數成本算術當成單位操作,並不是任意大 或成本的位元複雜度界:遮罩使用 個位元,精確累積成本也需要足夠位元。Python 整數避免固定寬度溢位,但不會令大整數算術免費。
反例模式
以最短路徑距離補上缺邊,會改變題目
假設只有 、、、 四條弧,成本都為 1。原圖沒有哈密頓巡迴:由 0 必須先到 1,再到 2,但沒有 。
若把每對頂點都替換成最短路徑距離,就得到完整距離矩陣。其巡迴 的成本為 ,但最後一段距離展開為 ,使原圖行走成為 ,重訪頂點 1。至少到訪每個頂點一次的閉合行走,與輸入圖中的哈密頓巡迴,是不同的最優化問題。
子集動態規劃的用途不限於這個目標。可重用的思考是:找出決定未來選擇的資訊,證明便宜的等價前綴可以替換昂貴前綴,再用嚴格遞增的量排列轉移。單有已訪集合、單有終點,或一個未解釋的位元遮罩,都不是正確性證明。
練習與完整解答
快速檢查
(四個頂點且位元 0 在右方時,把 編碼成遮罩。遮罩能否判斷路徑先到訪 還是 ?終點 對此狀態是否合法?)
把成員對應的二的冪相加。
解答 · 答案
遮罩是 ,寫成 1101。兩種到訪次序都會產生同一遮罩,所以它不記錄次序。終點 1 不合法,因為 。可達狀態還須有使用現存邊的真實路徑;語法上合法的遮罩及終點不保證可達。
快速檢查
(在四頂點矩陣中,計算 及 ,再用兩個候選算出 。)
把頂點 接在兩條路徑之後。
解答 · 答案
兩個較小狀態的路徑是 ,成本 ,及 ,成本 。接上頂點 3 後,候選為 及 ,最小值為 。再加收尾邊 ,巡迴成本便是 。
快速檢查
(兩頂點只有非對角成本 、。函數傳回甚麼?若回程邊不存在呢?只有一個頂點、對角項為 又如何?)
缺邊是 None,不是零。
解答 · 答案
兩條弧都存在時,答案是成本 、路線 。零成本邊不能誤當成缺邊。移除 後,雖然仍有全集路徑,卻沒有巡迴,故傳回 None。單頂點則按明確採用的零邊約定,傳回 ,忽略對角項 。
快速檢查
(三頂點的終點反例中,為何 不是合法的零成本答案?哪個狀態保留真正最優路線所需的前綴?)
看路線重複到訪哪個頂點。
解答 · 答案
路線在返回 0 之前到訪頂點 2 兩次,所以不是哈密頓巡迴。所需前綴為 ,狀態是 。它可以合法接上未訪頂點 2,再返回 0,總成本為 1。較便宜但同在 1 結束的狀態,已訪集合是 ,不能再接上 2,而且沒有返回 0 的邊。
快速檢查
(由父項狀態 、、、 重構巡迴。為何父項要同時按遮罩及終點儲存,不能只按終點?)
由後向前讀出終點,再倒轉。
解答 · 答案
反向讀終點得到 ,倒轉後再加最後的 0,得到 。每步移除目前終點的位元。同一終點對不同已訪集合,可能透過不同頂點才最便宜;每個終點只存一個父項,可能拼接不相關狀態,導致頂點重複或遺漏。每個狀態對各有父項,才保留產生所存成本的遞推關係。
快速檢查
(為何界是 ,而不是多項式?有些貪心最短路徑算法要求邊權非負,為何這裏容許負邊?)
先數狀態,再想每次轉移對已訪集合做了甚麼。
解答 · 答案
至多有 個子集,每個子集有 個終點,每個狀態至多有 個延伸,故算術操作為 。指數因子仍在,這不是多項式時間保證。負邊不破壞遞推,因為每次轉移都嚴格擴大已訪集合。依賴圖無環,而且有限多條簡單路徑中,最小值必定能實現。正確性來自精確狀態分解,不是貪心地把目前最短距離定案。