動機
局部搜尋可以透過改變一個變量來修復一個未被滿足的約束,但這一修復可能破壞原本已被滿足的約束。對於 2-SAT,只要公式可滿足,一個簡單的隨機漫步就能在多項式期望時間內找到滿足賦值。其分析把當前賦值與一個固定的滿足賦值作比較,而算法本身無須知道這個賦值。
在每一個未成功的步驟中,向滿足賦值靠近的概率至少為二分之一。我們並不假設各步相互獨立,而是使用一個具有負條件漂移的距離勢函數。再透過有限的時間上限和相互獨立的重新開始,把期望時間的論證轉化為單側錯誤的概率保證。
定義
模型與算法
定義 5.3.1
(2-CNF 公式)
2-CNF 公式是若干子句的合取,每個子句至多含兩個文字。文字是一個布爾(Boolean)變量或其否定。去掉恆真子句以及子句內重複的文字;若出現空子句,則立即報告不可滿足。若沒有剩餘子句,則返回任意賦值。在其餘情形下,令 為變量個數,並設每個子句含一個或兩個互異且互不相反的文字。
定義 5.3.2
(隨機漫步搜尋)
從任意賦值出發。只要當前賦值不滿足該公式,就選取任一當前未被滿足的子句,在其變量中均勻隨機地選取一個,並翻轉該變量。子句的選取可以依賴於整個過去;而在該子句的變量之間所作的隨機選擇,在給定歷史的條件下是全新且均勻的。若當前賦值滿足所有子句,則返回該賦值。
定理
定理 5.3.3
(可滿足公式上的期望搜尋時間)
若公式有滿足賦值,則從任一初始賦值出發,隨機漫步首次到達某個滿足賦值之前的期望翻轉次數至多為 。
定理 5.3.4
(設有上限的單側隨機化程序)
讓漫步至多運行 次翻轉,並檢查所得賦值。對於可滿足公式,該次運行未能找到滿足賦值的概率至多為 。使用全新且相互獨立的隨機選擇重複 次運行,可使失敗概率至多為 。即使公式不可滿足,所返回的任何賦值也都可被驗證為滿足賦值。
若所有運行均失敗,設有上限的程序返回「未找到」。該結果不是不可滿足性的證明。定理只在存在滿足賦值時才界定其概率。
證明
固定的滿足賦值帶來進展
為方便分析,固定任一滿足賦值 。令 為當前賦值與 之間的漢明(Hamming)距離,即兩者取值不同的變量個數。算法並不知道 ,也從不計算 。
引理 5.3.5
(向固定解靠近的進展)
設 為一個滿足賦值, 為當前賦值與 之間的漢明距離。在到達滿足賦值之前的每一步,在給定整個歷史的條件下,下一次翻轉使 減一的概率至少為 ,否則使它加一。若所選子句只含一個變量,或 ,則減小的概率為一。
證明
(為甚麼假子句帶來進展)
在一個不滿足公式的賦值處,所選子句為假。由於 滿足該子句,該子句中至少有一個文字在當前賦值與 之間由假變為真。因此它的變量與 不同。一個子句至多含兩個互異變量,所以均勻翻轉使 減小的條件概率至少為二分之一。任何被翻轉的變量要麼與 一致,使距離增加一;要麼與 不一致,使距離減少一。對於單文字子句,距離以概率一減小。
若 ,則每個變量都與 不同,故每一種可能的翻轉都使距離減小。若 ,則當前賦值等於 ,已經是滿足賦值。距離過程可能依賴於先前的子句選擇,但在終止之前,該條件下界對每一種容許的歷史都成立。
勢函數及其條件漂移
證明
(借助勢函數估計期望時間)
對 定義 。它非負且至多為 。對於 ,令 。則
若距離減小的概率為 ,則條件期望變化至多為
在 處,距離以概率一減小,且 。因此,在找到滿足賦值之前的每一步,勢函數的條件期望至少下降一。
令 為首次到達滿足賦值的時間(以翻轉次數計),並在該時間之後凍結過程。對前 次可能的翻轉累加條件漂移並取期望,得到
左側非負,故 。令 趨於無窮並利用單調收斂定理,得 。特別地,漫步幾乎必然到達某個滿足賦值。它可能更早到達一個不同於固定的 的滿足賦值;在第一個滿足賦值處凍結只會對論證有利。
證明透視
勢函數與停時各自的作用
每個假設都恰在一處使用。子句大小至多為二,給出減小的概率 ;對 有 ,於是 ;在 處則必然減小。不顯然的一步是選用二次勢函數。距離本身的期望變化為 ,公平的一步為零,對終止性毫無說明;而凹函數 把每個公平的一步變成恰為 的漂移。
論證通過停時收束。對每個有限的 , 的界都成立; 的非負性把它變成 的界;再用單調收斂令 。證明沒有用到 的馬爾可夫(Markov)性,只用到在每個歷史之下的漂移界。
漂移界是關於條件期望的陳述,並不是關於單次翻轉的陳述。
反例模式
靠近的機會均等並不意味著單調進展
一次翻轉可能增大與固定解的距離。例如,當一個為假的雙文字子句含有一個與 一致的變量和一個與 不一致的變量時,均勻翻轉以各二分之一的概率向任一方向移動。具體地,在下面的兩個變量的例題中,漫步位於 時假子句為 ;翻轉 得到 ,它與解 的距離為 ,而原來的距離是 。證明所用的是彎曲勢函數的期望下降,而不是聲稱每次翻轉都改進賦值。
為甚麼這個勢函數的形狀恰到好處
考慮距離為 的理想化無偏漫步,設距離零為吸收態,距離 總是移動到 。若 是其到達零的期望時間,則一步方程給出
其中 。代入 可滿足所有這些方程。這一觀察啟發了勢函數的選取:它正是參照漫步的期望時間的精確解;而對於這個遞增的凹函數,向下移動的可能性不低於參照漫步的過程,其條件期望變化不會更大。
證明並不要求實際的距離過程是馬爾可夫鏈。兩個歷史可能具有相同的距離,卻有不同的當前賦值和不同的可用假子句。條件漂移不等式對每個這樣的歷史都成立,所以累加仍然有效。若不加論證地把距離當作獨立的對稱隨機漫步,就會忽略這一區別。
參照方程也解釋了為甚麼線性距離勢函數在此不夠用:公平的一步其距離的期望變化為零,而二次勢函數的二階差分貢獻嚴格為負。子句大小的上界對這一特定論證同樣至關重要。若有三個互異文字,一個假子句可能只需有一個變量與固定的滿足賦值不同,從而使減小的概率低至三分之一。例如,在 處子句 為假,而滿足賦值 僅在 上不同。在其三個變量中均勻選擇,向該所選解靠近的概率為三分之一。這並不證明隨機漫步對 3-SAT 無益;它說明的是為何二分之一漂移的證明不能原封不動地照搬。
最後,勢函數可能停在正值上,因為漫步可能到達一個不同於分析中所固定的那個滿足賦值。裂項求和的界只要求停止後的勢函數非負。要求它恰為零,會增加一個不必要且一般而言不成立的假設。
從期望時間到有限上限
證明
(馬爾可夫不等式與重新開始)
馬爾可夫不等式給出 。檢查初始賦值以及每次翻轉之後的賦值,可確保在上限之前到達的滿足狀態被返回。若一次運行失敗,則從任意賦值出發,使用全新的隨機選擇重新開始。同樣的條件界適用於每次運行,所以全部 次運行都失敗的概率至多為 。
對於不可滿足的公式,沒有任何賦值能通過明確的子句檢查,所以該程序絕不會返回虛假的滿足賦值。它的「未找到」結果無法區分不可滿足的公式與可滿足公式上運氣不佳的一次運行。這是一種隨機化搜尋保證,而不是不可滿足性的獨立證明。
設有 個子句,直接的實現為找到一個未被滿足的子句而檢查所有子句,每次翻轉需要 時間,初始化一個賦值需要 時間。在文字求值為常數時間的假設下, 次設有上限的運行在預處理之後共需 時間。在雙文字子句中選擇變量使用一個公平位元;單文字子句則無須隨機位元。一次運行至多使用 個這樣的位元。2-SAT 存在更快的確定性算法;本章分析的是隨機漫步方法,並不聲稱它是最快的方法。
例題詳解
例題 5.3.6
(兩個變量的漫步)
考慮 ,其唯一的滿足賦值為 。從 出發,第一個子句為假。翻轉任一變量得到 或 ,各以二分之一的概率出現。從任一狀態出發,唯一的假子句都含有一個通向 的翻轉和一個回到 的翻轉。因此在最初兩次翻轉內成功的概率為 。
例題 5.3.7
(單位子句)
對於公式 ,從 出發,選取唯一的變量並把它翻轉為一。漫步在一次翻轉內成功。條件減小概率為一,強於下界二分之一。
例題 5.3.8
(不可滿足的實例)
對於 ,沒有任何賦值能同時滿足兩個子句。在任一賦值處恰有一個單位子句為假,若無上限,漫步將永遠翻轉 。設有上限的程序返回「未找到」;它從不聲稱存在滿足賦值。
例題 5.3.9
(重新開始放大成功概率)
若對一個可滿足公式獨立運行四次,每次上限為 次翻轉,則四次運行全部失敗的概率至多為 。當找到滿足賦值時,運行可能提前停止。這個估計是最壞情形的界,而不是對每個公式都精確的失敗概率。
常見錯誤
常見錯誤
(假子句不必所有變量都與解不同)
一個假子句含有與某個特定解不同的變量,並不意味著該子句中的每個變量都與之不同。均勻選取一個變量翻轉,可能遠離該解。證明只需要「減小」的條件概率至少為二分之一。
常見錯誤
(期望時間並不是每次運行的上界)
期望時間的結果並不對每一次運行提供確定性的上界。隨機選擇可能反覆回到相同的賦值。上限給出一個帶有明確失敗概率的有限程序;重複運行會降低該概率,但在有限次運行之後並不能使之為零。
常見錯誤
(搜尋失敗並不證明不可滿足)
最後,隨機搜尋失敗並不證明公式不可滿足。在此算法中,只有返回的賦值才是證書。另一個確定性的 2-SAT 算法可以判定這兩種答案。
總結
對於可滿足的 2-CNF 公式,每個假子句都含有一個與固定解不一致的變量。隨機翻轉使漢明距離減小的條件概率至少為二分之一。勢函數 在找到滿足賦值之前,期望漂移至多為負一,由此得到 的期望翻轉次數上界。加上限並重新開始,便得到一個有限的單側隨機化搜尋程序。
練習
快速檢查
(對於公式 ,從 出發,當 時,計算翻轉次數及勢函數的下降量。)
計算 。
解答 · 答案
一次翻轉把 變為一並滿足該子句。與解的距離由一變為零;,,所以勢函數下降一。
快速檢查
(在兩個變量的例題中,計算從 出發在兩次翻轉內成功的概率。)
列出兩種等可能的第一次翻轉,並分別跟進。
解答 · 答案
第一次翻轉之後,狀態為 或 。在兩種情形下,對該假子句的兩種等可能翻轉中,都有一種到達 。因此概率為 。
快速檢查
(若每次設有上限的運行失敗的概率至多為二分之一,需要多少次獨立運行才足以使失敗概率至多為 ?)
解 。
解答 · 答案
五次運行即足夠,因為 。
快速檢查
(解釋為甚麼在一次設有上限的運行失敗後返回「不可滿足」是不合理的。)
在可滿足公式上運氣不佳的一次運行,會不會看起來一樣?
解答 · 答案
可滿足的公式也可能出現運氣不佳的翻轉序列,使得在上限之前沒有到達滿足賦值。算法只能控制這種失敗的概率;它並不產生不存在任何滿足賦值的證書。