動機
一條送貨路線必須到訪每一個地點,並返回起點。尋找成本最低的路線可能十分困難,但近似算法能夠給出一條路線,並證明其成本相對於未知最優值的比例。對於度量距離,最小生成樹給出一個有用的下界,而沿該樹繞行一周的途徑可以給出成本至多為最優值兩倍的巡迴。
三角不等式使我們可以刪去重複到訪而不增加成本。我們亦會說明,對樹中奇度頂點作配對,可以把論證改進為因子 ;這裏假設存在精確的最小權完美匹配算法,並視之為一個獨立的計算要素。
定義
定義 4.4.1
(度量實例)
設 是含 個頂點的有限集。對每一對有序頂點 ,令 ,且 ,,。不同的頂點之間的距離可以為零。由此得到的完全無向加權圖在本章所需的意義下是度量的。
定義 4.4.2
(巡迴與最優值)
巡迴(tour)是一條閉途徑,它恰好到訪每個頂點一次,然後返回起點。當 時,巡迴把唯一的一條無向邊走兩次。記 為最小的巡迴成本。途徑(walk)可以重複頂點或邊;每一次經過都貢獻相應的距離。若 ,則零成本的原地巡迴是最優的,可以單獨返回。
定義 4.4.3
(生成樹、多重圖與歐拉途徑)
最小生成樹(MST)是權最小的、連通且無圈的生成子圖。多重圖可以含有同一條邊的平行副本;頂點的度數計入每一個副本。連通且各頂點度數均為偶數的多重圖的歐拉(Euler)迴路,是恰好經過每個邊副本一次並返回起點的閉途徑。標準的歐拉迴路構造沿著未使用的邊前進並拼接閉途徑;其運行時間與邊副本的數目成線性關係。
定理
定理 4.4.4
(雙倍樹近似)
將最小生成樹的每條邊加倍,對其歐拉迴路按首次到訪進行捷徑處理,得到的巡迴成本至多為 。
定理 4.4.5
(奇度頂點配對的改進)
設 為某棵 MST 的奇度頂點集。若把 上的一個精確最小權完美匹配加入該樹,則所得多重圖的歐拉迴路可以經捷徑處理為成本至多為 的巡迴。
上的完美匹配把其頂點劃分為互不相交的數對,每一對使用一條邊;當 時取空匹配。第二個定理假設這樣的最小權匹配可以被計算出來。一般圖上加權完美匹配的多項式時間算法是另一個獨立的結果,本章不予證明。
證明
生成樹下界
引理 4.4.6
(最小生成樹的下界)
給 上的完全圖賦予非負邊權,並設 為最小生成樹。則 。
證明
(刪去最優巡迴的一條邊)
取一條最優巡迴。當 時,刪去其任意一條邊,其餘的邊構成一條生成路徑,因而是一棵生成樹;由於邊權非負,它的成本不超過該巡迴的成本。當 時,刪去兩次經過中的一次,剩下唯一的生成邊,其成本同樣不超過巡迴成本。MST 不比這棵樹更昂貴,故
這一論證不需要三角不等式。它利用完全性來保證巡迴存在,並利用權的非負性來說明刪去一條邊不會增加成本。
加倍樹並對途徑作捷徑處理
證明
(加倍樹,再取捷徑)
將 MST 的每條邊加倍。所得連通多重圖的每個頂點度數均為偶數,因此存在歐拉迴路,其成本恰為 。它可能多次到訪同一頂點,所以還不是旅行推銷員的巡迴。
從選定的起點出發,按歐拉途徑首次到訪各頂點的次序列出這些頂點。把相鄰的兩個列出頂點直接相連,再把最後一個頂點連回起點。每個頂點在返回之前恰好出現一次。每條直接邊都替換了原途徑中連續的一段。反覆應用三角不等式可知,該直接邊的成本不超過被替換的那一段。這些片段(包括最後返回起點的片段)構成原途徑的一個劃分,因此捷徑巡迴的成本至多為 。
對於兩個頂點,捷徑處理後剩下這兩個頂點之間那條邊的兩次相反方向的經過,恰好是所需的閉巡迴。零權邊不會造成問題;所有不等式都是非嚴格的。若 ,證明給出成本為零的巡迴。乘積形式的陳述仍然作為不等式有意義,而無須除以零。
證明透視
上界與下界在樹上交會
因子二來自三個互不相同的步驟,每一步用到不同的假設。刪去最優巡迴的一條邊只用到邊權非負,給出 。把樹加倍完全不用距離:它只是令每個度數變成偶數,因此存在成本恰為 的歐拉途徑。捷徑是唯一用到三角不等式的步驟,被它換成直接邊的每一段途徑各用一次。把三者連起來,捷徑巡迴的成本至多為 ,而 。
配對奇度頂點
證明
(奇偶性、交替匹配與捷徑)
有限無向圖中奇度頂點的數目為偶數,因為度數之和等於邊數的兩倍。設 為 的奇度頂點集, 為 上的一個最小權完美匹配。把 加到 上,恰好改變 中各頂點的奇偶性,使每個頂點的度數變為偶數。結果仍然連通,因此存在成本為 的歐拉迴路。
我們證明 。沿著一條最優巡迴走一遍,只保留 中的頂點,並在相鄰的保留頂點之間作捷徑處理。由三角不等式,所得 上的閉途徑不比原巡迴更昂貴。當 時,它的圈上各邊交替地分成兩個完美匹配。這兩個匹配的成本之和就是該途徑的成本,所以較便宜的那個匹配的成本至多為其一半。最小匹配 不比該匹配更昂貴。
當 時,捷徑得到的閉途徑沿兩個方向各經過這兩個奇度頂點之間的那條邊一次。把這兩次經過視為該邊的兩個副本,便得到兩個單邊的完美匹配,每個的成本都等於該邊的成本;同樣得到成本至多為一半的結論。當 時, 為空,成本為零。因此在所有情形下 。
歐拉途徑的成本至多為 。按首次到訪對其作捷徑處理不會增加成本,因此最終的巡迴滿足第二個定理。即使存在多棵 MST、多個最小匹配或多條最優巡迴並列的情形,這個證明依然給出成本保證。
證明透視
配對界從何而來
度數的握手奇偶性只用了一次: 是偶數,所以完美配對存在,加入它之後每個度數都變成偶數。三角不等式用了兩次,一次是把最優巡迴縮短到只經過 ,另一次是對最後的歐拉途徑作捷徑處理。關鍵一步是:經過偶數個頂點的閉途徑可以分成兩個配對,所以其中較便宜的一個成本至多是該途徑的一半。 的最小性使它可以與這個較便宜的配對相比較。
算法成本與適用範圍
完全圖有 條邊。MST 可以在多項式時間內求得;例如,Prim 算法的合適的陣列實現在稠密圖上需要 次比較。將其 條邊加倍、求歐拉迴路並作捷徑處理,在直接的表示下需要 或更少的時間。因此,因子二的算法對於顯式距離矩陣的輸入大小是多項式的。
對於因子 的算法,還需加上在至多 個奇度頂點上運行精確最小權完美匹配程序的成本。已知在適當的精確算術假設下,這類程序對一般加權圖是多項式時間的,但本章不證明該算法及其位元複雜度。近似性的證明以取得最小匹配為條件,而不是針對一個僅僅看起來很短的貪心配對。
若距離為有理數或整數,算術運算的次數並不自動等於位元時間界。實現時必須準確地表示和並準確地比較權。該定理針對滿足所有度量假設的精確距離;浮點捨入可能需要另行分析。
例題詳解
例題 4.4.7
(三個等距頂點)
設每一對不同頂點的距離均為一。MST 有兩條邊,成本為二。將其加倍得到成本為四的歐拉途徑。對重複頂點作捷徑處理,得到由三條邊組成、成本為三的巡迴,它是最優的。因子二的保證容許成本高達六;這只是上界,並不預示算法總是付出最優值的兩倍。
概念視角算法
加倍樹巡迴就是前序遍歷
取定根,沿深度優先的途徑走:每條邊向下走一次、向上走一次;這是加倍樹的一條歐拉巡迴。按首次到訪的次序排列頂點,恰好就是有根樹的前序。所以這個算法就是:求最小生成樹,按前序列出它的頂點,然後回到根。
例題 4.4.8
(四個頂點的直線度量)
把頂點放在數線上的座標 處,距離等於差的絕對值。依次經過相鄰座標的路徑是成本為三的 MST。巡迴 的成本為 ;雙倍樹途徑可以經捷徑處理得到這條巡迴。該路徑的奇度頂點集由它的兩個端點組成,其配對的成本為三,所以配對構造同樣得到成本為六的途徑。
例題 4.4.9
(兩個頂點的邊界情形)
對於距離為 的兩個頂點,MST 的成本為 ,所需的閉巡迴成本為 。樹的兩個頂點度數都是奇數,它們的完美匹配就是那條成本為 的邊。把它作為第二個邊副本加入,得到成本為 的歐拉迴路,恰好是最優的。
例題 4.4.10
(捷徑處理需要三角不等式)
設三條邊的成本為 ,,。加倍的路徑 的成本為四。捷徑處理為 後成本為十二,因此捷徑反而增加了成本。這些數值違反三角不等式,因為 ;度量近似的證明不適用。
反例模式
途徑並不自動是巡迴
聲稱:加倍 MST 的歐拉途徑本身已經是旅行推銷員巡迴。取四個頂點 ,任意兩點距離都是 ;這是一個度量。以 為中心、 為葉子的星形是成本為 的 MST。把它加倍得到歐拉途徑 ,成本為 ,它四次經過 ,所以不是巡迴。按首次到訪作捷徑處理,得到 ,成本為 。正確的說法是:途徑要經過捷徑處理才成為巡迴,而三角不等式(這裏是每段被取代路程的 )保證捷徑巡迴的成本不超過原途徑。
常見錯誤
常見錯誤
(生成樹不是巡迴)
MST 是最優巡迴的下界,但它本身不是巡迴:它的葉子度數為奇數,而樹一般不能提供一條恰好到訪每個頂點一次的閉路線。加倍產生閉途徑,捷徑處理產生所需的巡迴。每一次變換都有各自的證明責任。
常見錯誤
(貪心配對不是最小匹配)
奇度頂點的配對必須把所有奇度頂點配對。僅僅貪心地把相鄰的頂點配對,可能得到比最小者更昂貴的完美匹配,所以證明 不能用於任意的配對。若匹配本身只用近似算法,則需要相應調整分析。
常見錯誤
(最優值是基準,不是輸入)
最後,該保證比較的是算法在同一實例上的結果與最優值。算法運行時不需要知道 。最優巡迴只出現在證明中,作為界定樹和匹配成本的基準。
總結
刪去巡迴的一條邊得到 MST 下界。將樹加倍使其度數為偶數,在度量中對歐拉途徑作捷徑處理,得到成本至多為最優值兩倍的巡迴。對樹的奇度頂點作配對,其成本至多為最優巡迴的一半,從而把界改進為 ,但以能夠計算最小完美匹配為條件。三角不等式、奇偶性與非負成本各自發揮不同的作用。
練習
快速檢查
(解釋為甚麼把樹的每條邊加倍後,每個頂點的度數都變為偶數。)
數一數一個頂點處的邊副本。
解答 · 答案
加倍之後,每條關聯邊貢獻兩個邊副本,所以每個原來的度數都乘以二,變為偶數。圖仍然連通。
快速檢查
(對於距離為 的兩頂點度量,計算 MST 的成本、最優巡迴的成本,以及加入匹配後的歐拉途徑的成本。)
參考兩個頂點的邊界例子。
解答 · 答案
MST 只有一條成本為七的邊。閉巡迴把該邊走兩次,成本為十四。兩個頂點在樹中的度數都是奇數;匹配加入一個成本為七的邊副本,得到成本為十四的歐拉途徑。
快速檢查
(為甚麼巡迴的成本是 MST 成本的上界?請明確說明權非負所起的作用。)
要刪去哪一條邊?
解答 · 答案
從至少含三個頂點的巡迴中刪去一條邊,剩下一條生成路徑,因而是一棵生成樹。因為被刪去的邊權非負,剩下的樹的成本至多等於巡迴的成本。MST 的成本不超過該樹的成本。對於兩個頂點,則刪去兩次經過中的一次。
快速檢查
(設 含有四個頂點,它們沿著一條經捷徑處理的最優巡迴按圈的次序排列,各邊成本為 。寫出兩個交替匹配,並界定最小匹配的成本。)
把圈上的邊交替分成兩組。
解答 · 答案
兩個交替邊集的成本分別為 與 。二者都是這四個頂點上的完美匹配,所以最小匹配的成本至多為 ,特別地,至多為捷徑巡迴成本 的一半,即 。