動機
局部搜尋算法從一個可行解出發,只要某個小改動能改進目標函數,就進行該改動。最終得到的解未必是全局最優的,但「不存在任何容許的改進」這一事實本身就可以推出有用的近似保證。最大割問題給出了一個特別清晰的例子:當沒有任何頂點能透過移到另一側而獲益時,至少有一半的總邊權被割開。
解的質素的證明與算法終止性的證明是兩件獨立的事。對於任意非負實數權重,嚴格改進規則之所以會終止,是因為割只有有限多個,但這一觀察並不能給出關於輸入長度的多項式界。對於整數權重,每次改進至少為一,從而得到以總權重的數值大小表示的界。
定義
定義 1.1.1
(割的值)
設 為有限無向無自環圖,各邊帶有非負權重 。容許平行邊,且平行邊分別計數。割是 的一個劃分,分成兩側。其值 是兩個端點位於不同側的邊的權重之和。記 ,並令 為最大的割值。由於權重非負,。
定義 1.1.2
(頂點增益與單頂點局部最優)
對割中的頂點 ,記 為與其關聯的被割邊的總權重, 為與其關聯的未被割邊的總權重。單獨把 移到另一側,割值的變化量為 。若沒有任何單次移動能嚴格增大割值,即對每個頂點都有 ,則稱該割為單頂點局部最優。
定理
定理 1.1.3
(局部最優解的質素)
在有限無自環且權重非負的圖中,每個單頂點局部最優割的值至少為 ,因而至少為 。
定理 1.1.4
(嚴格改進的終止性)
從任意割出發,反覆移動滿足 的頂點,必在某個單頂點局部最優割處終止。若所有邊權均為非負整數,則至多進行 次移動。僅憑這一數值上的界,未必是關於二進制輸入長度的多項式界。
證明思路或證明
證明
(雙重計數,再由嚴格改進得到終止)
在局部最優解處,對所有頂點把 求和。每條被割的邊在左邊於其兩個端點處各被計數一次,而每條未被割的邊在右邊於其兩個端點處各被計數一次。於是 ,即 。由於任何割的權重都不超過 ,故 。無自環的假設保證移動一個頂點會改變每條關聯邊的狀態;自環將始終保持未被割,除非另行處理,否則會令所述的移動公式失效。
每次嚴格改進的移動都會增大目標函數。頂點到兩側的分配只有有限多種,所以同一個割不可能被重複訪問,過程必然終止。終止時沒有任何頂點具有正的增益,這恰好就是局部最優性條件。對於整數權重,每個正增益都是不小於一的整數。目標函數從非負值開始,且永不超過 ,因此至多有 次移動。以二進制書寫的數可以比其表示長度大出指數倍,這就是為甚麼這只是一個數值意義上的保證,而不是多項式時間保證。
證明透視
雙重計數給出保證
局部不等式是針對每個頂點的。把它們相加時,每條邊被計數兩次,即在每個端點各一次;這就把眾多局部命題轉化為被割權重與未割權重之間的一個整體比較。
例題詳解
例題 1.1.5
(三角形)
給三角形的每條邊賦權為一。一側一個頂點、另一側兩個頂點的割,其值為二。單獨的那個頂點的被割權重為二,未割權重為零;另外任一頂點的關聯被割權重與未割權重各為一。沒有任何單次移動能嚴格改進該割。最優值為二,因為三角形的三條邊不可能全部被割開。
例題 1.1.6
(一次嚴格改進)
對於單位權重的路徑 ,從所有頂點在同一側開始。割值為零。移動 會使兩條邊都由未割變為被割,割值增加二。所得割的值為二,等於總權重,因而是最優的。
例題 1.1.7
(局部最優割不必是全局最優)
對於單位邊權的四邊形(四個頂點的圈),將兩個相鄰頂點放在一側,另外兩個放在另一側。兩條相對的邊界邊被割,故 ;每個頂點恰有一條關聯邊被割、一條未被割,因此每一次單頂點移動的增益都為零。按嚴格改進的定義,這是一個局部最優解。若讓兩側交替分配,則四條邊全部被割,值為四。比值 表明,對於任意的單頂點局部最優解,該定理中的因子是緊的。
常見錯誤
反例模式
不存在改進的單次移動並不意味著全局最優
上面的四邊形割無法透過移動一個頂點來改進,但移到交替劃分後其值翻倍。局部最優性總是相對於所容許的鄰域而言的。
常見錯誤
(零增益移動可能循環)
若容許零增益移動而沒有防循環規則,則可能永遠重複訪問同一個割。終止性的證明用到的是嚴格改進。此外,在把 轉化為對 的近似時,該結論依賴於權重非負;帶負權重的變體需要另行定義和分析。
解讀局部不等式
條件 表示,與每個頂點關聯的總權重中,至少有一半已經跨越了該割。這並不是說每條單獨的關聯邊都被割開。在四邊形的例子中,每個頂點有一條被割邊和一條未割邊,因此每個頂點處都可能取等號,而整體的割卻只有最優值的一半。
雙重計數恆等式可以明確寫成:
每條無自環的邊在其兩個端點處各貢獻一次權重,並且恰好屬於兩個類別之一。把局部不等式相加得到 。該論證同樣適用於非連通圖和孤立頂點。孤立頂點有 ,它位於哪一側對目標函數沒有影響。
例題 1.1.8
(帶權局部檢驗)
取路徑 ,邊權為 ,。在割 中,割值為 。在 處,;在 處為 ;在 處為 。最後一個頂點具有正增益 ,所以這個割不是局部最優的。移動 得到 ,兩條邊都被割開,值為 。
嚴格改進與運行時間
一個實現可以掃描各頂點,找到增益為正的頂點,移動它,然後重複。在每一步,當前的分配都是一個合法的割。移動之後,被移動頂點及其鄰點的增益可能發生變化;非鄰點的增益不變。維護增益的實現必須一致地更新這些增益,並且在宣告局部最優之前必須檢查所有頂點。一次完整的掃描即給出直接的證書:報告每一對 ,並檢驗 。
有限狀態的終止性論證適用於任意實數權重,包括無理數權重,因為嚴格增大使得不可能回到任何先前的割。把頂點分配到兩個有標記的側,至多有 種分配。這是不同分配個數的指數上界,而不是多項式時間保證。若把兩側視為可互換的,則不同的無標記割的數目可以減少,但這並不改變「需要做複雜度分析」這一結論。
對於整數權重,增益是整數,因此每次嚴格移動至少使割值增加一。若 ,則每條邊的權重為零,每個割已經是局部最優的,不會發生移動。若 ,則無論選擇改進頂點的規則如何,移動次數都以 為界。由於 的位元長度是其數值大小的對數,這為樸素算法給出了一個偽多項式界。更強的多項式時間結果需要不同的論證或算法,此處並未建立。
近似與邊界情形
對於最大化問題, 近似保證即 。比值 僅在 時才有意義。若所有權重為零,該不等式仍然成立,即 ,而商 則沒有定義。直接陳述不等式可以處理這一邊界情形,而無需臆造數值比值。
該證明把局部割與 作比較, 是一個容易計算的上界。它可能是一個較弱的界:在單位權重的三角形中,,但最優值為二。三角形的任何割都不可能包含全部三條邊,這一更強的觀察是該圖所特有的。局部搜尋的證明不需要這樣的結構分析,在所述假設下適用於每一個圖。
隨機割獨立地把每個頂點分配到某一側,其期望值為 。該平均論證證明了存在一個至少與總權重一半同樣好的割,但某次隨機實現可能更差。局部搜尋定理則是在其單頂點規則下,保證每個終止割的質素。兩種論證共享同一個界,而依據的證據不同:一個是期望,另一個是逐頂點不等式。
常見錯誤
(取到一半界的等號不能證明最優)
四邊形還說明,僅憑取到一半界的等號並不能證明最優性。在其相鄰兩點的割中,雙重計數不等式的兩邊相等,但最優值是局部值的兩倍。要改進近似保證,需要額外的算法思想或更大的鄰域,並配以新的證明;所展示的定理並未作出這樣的斷言。
檢驗一個給定的終止割
讀者無需重放移動序列,就可以驗證所聲稱的局部最優解。列出劃分的兩側,計算割值,並對每個頂點分別對同側鄰點和異側鄰點求關聯權重之和。若每個異側之和都不小於同側之和,則該割是局部最優的。隨後由雙重計數的證明給出近似不等式。若哪怕只有一個頂點違反該不等式,移動它就給出一個顯式的嚴格更優的割,從而否定該局部最優性的聲稱。
這一檢驗也清楚地表明該保證依賴於哪些數據。權重必須是所評估實例的權重,並且每條邊都必須按其所述的重數計數。平行邊對端點和以及對 都是各自獨立貢獻的。該證明並不要求特定的初始劃分或特定的改進頂點序列,因此不同的運行可以終止於不同的局部最優解,而每一個都具有同樣的「至少總權重一半」的保證。
局部最優性的證書弱於全局最優性的證書。要證明帶權路徑例子中的全局最優性,還需給出一個值為 的割,與普適上界相匹配。在四邊形的例子中,局部不等式成立,但存在更好的割,從而否定了全局最優性。把這兩種斷言分開,可以避免把算法的停止條件誤當作「沒有任何多頂點改動能起作用」的證明。
把半總權重的保證化為確定性構造
前面的局部搜尋證明使用終止割上的逐頂點不等式。還有另一種構造半權重割的方法:逐個固定頂點,同時保持條件期望。設圖有限、無向、沒有自環,邊權非負,總權重為 。先設想每個頂點獨立地以各 的概率放到 或 。每條邊的端點分處兩側的概率為 ,所以割值期望是 。這裏使用的是期望的線性性;各邊是否被割開的指示變量不必互相獨立。
固定部分頂點後,仍把未固定頂點視為將獨立地擲公平硬幣決定位置。記這種假想補全的割值期望為 :兩端已固定且跨割的邊貢獻全部權重;兩端已固定且同側的邊貢獻零;至少一端未固定的邊貢獻其權重的一半。對下一個頂點 ,記固定為 、 後的期望分別為 。由於硬幣的兩個結果等可能,
因此 至少有一個不小於 。選擇其中較大者,平手時任選一側,再繼續處理。空賦值的期望為 ,按此規則所得的期望序列不會下降。所有頂點固定後不再有隨機性, 就是構造出的實際割值 ,所以 。邊權非負保證 ; 時不等式仍成立,但比值 沒有定義。這是確定性構造,並不是說每個隨機割都達到期望值。
例題 1.1.9
(另一個加權三角形)
這裏使用與上面單位權例子不同的三角形:、、,故 。按 的次序固定頂點,本次在平手時選擇 。表中是精確條件期望,並非隨機模擬的平均值。
| 下一個頂點 | 選擇 | 保留的 | ||
|---|---|---|---|---|
起初 。固定 後, 已跨割,貢獻 ;另外兩邊尚未完全固定,貢獻 ,於是 。最後取 ,邊 跨割而 不跨割,實際割值為 。一般保證只要求至少 ;這裏得到較大的值,是此實例和這些選擇的結果。
從空賦值保持 的證明要求每一步都比較並選擇較大的期望。若手動選了較差的一側,此後繼續選較大者只能保證不低於新前綴的期望,未必能補回先前的損失。例如先取 ,再取 , 降至 ;餘下最好的選擇是 ,最終割值 。因此從手動前綴繼續完成,不能事後補證原來的半權重保證。
實現時,決定 的兩側選擇差異的只有它連向已固定鄰點的邊:通向未固定鄰點的邊在兩種選擇下都貢獻一半權重。分別求出 連向左右兩側已固定鄰點的權重之和,把 放到較大總和的對側。使用鄰接表時,每條邊在其兩個端點處各檢查一次,整次構造需 次算術操作;位元複雜度仍取決於輸入表示和精確運算。這一構造未必得到單頂點局部最優割;它的證明依據是持續保持條件期望,而非前面的局部不等式。
總結
在單頂點局部最優解處,每個頂點的關聯被割權重都不小於未割權重。雙重計數給出「至少總權重一半」的保證。嚴格改進必然終止,但整數權重情形下的數值界不可與多項式位元複雜度界混為一談。
練習
快速檢查
(在單位權重的三角形中,對例中割的兩頂點一側,驗證局部不等式。)
把一個頂點上被割與未被割的關聯邊權重分別加起來。
解答 · 答案
這兩個頂點中的每一個,都有一條邊連向單獨的那個頂點,另有一條邊連向其同側的另一個頂點。因此 。
快速檢查
(在三個頂點且未被割的單位權重路徑中,移動中間頂點的增益是多少?)
比較移動前後兩條關聯邊的狀態。
解答 · 答案
兩條關聯邊都變為被割,所以增益為 。
快速檢查
(為甚麼四邊形的例子是局部最優的,卻不是全局最優的?)
先算一個頂點的增益,再與交替割比較。
解答 · 答案
每個頂點恰有一條被割的關聯邊和一條未被割的關聯邊,因此其增益為零。交替割的值為四,而不是二。
快速檢查
(若整數權重之和為 ,該定理對嚴格改進移動次數給出甚麼上界?)
每次嚴格移動使整數的割值至少增加一。
解答 · 答案
至多 次:整數割值每次移動至少增加一,且永不超過總權重。