隨機約束滿足問題相變研究綜述*

牛鵬飛,王曉峰,2,蘆 磊,張九龍

(1.北方民族大學計算機科學與工程學院，寧夏 銀川 750021； 2.北方民族大學圖像圖形智能處理國家民委重點實驗室，寧夏 銀川 750021)

1 引言

隨機約束滿足問題RCSPs(Random Constraint Satisfaction Problems)由一組變量和變量的約束條件組成。對約束滿足問題求解就是對所有變量尋求一組賦值使得所有約束條件都被滿足的過程。該問題在模式識別、時序推理和機器人路線規劃等應用廣泛。理論計算機科學和人工智能領域很多NP-完全問題本質上都可用約束滿足問題來表示，因此，研究約束滿足問題具有很強的理論意義和實際應用價值。對約束滿足問題進行深入研究不僅可以探索該問題難解的原因，還可以從統計物理學和數學等交叉方向解析約束滿足問題相變現象的本質，并據此為設計高效的求解算法奠定理論基礎[1]。

1991年，Cheeseman等[2]發現在約束滿足問題中存在約束密度，隨著約束密度的不斷增大，RCSPs會發生可滿足相變現象。之后文獻[3]揭示了隨機約束滿足問題的解空間變化更為復雜，在可滿足相變之前，會依次發生聚類相變、冷凝相變和剛性相變等幾類不可滿足相變現象，這說明相變點附近不僅包含問題最難解的實例，而且在這幾個相變點附近，解空間的結構特征具有不同的代數統計性質和幾何統計性質。

隨機圖著色問題和隨機可滿足問題是隨機約束滿足問題中最重要的2個子問題，其中隨機可滿足問題是第一個被證明的NP-完全問題[4],隨機圖著色問題也是經典的組合優化問題。對隨機圖著色問題和隨機可滿足問題相變的研究主要是通過數值計算及算法分析、嚴格數學分析和統計物理分析3種不同思路的方法來展開的。

本文對近幾十年來隨機圖著色問題和隨機可滿足問題相變研究的相關成果進行了匯總。其中，第2節介紹隨機圖著色問題及其相關定義，對隨機圖著色問題的可滿足相變和不可滿足相變進行詳細綜述；第3節介紹隨機可滿足問題及其相關定義，對隨機可滿足問題的可滿足相變和不可滿足相變進行匯總；最后對隨機約束滿足問題未來的研究趨勢進行展望。

2 隨機圖著色的相變問題

給定一個無向圖G(V,E)，其中，V為頂點集合，E為邊集合，圖著色問題是指用q種顏色對頂點著色，并滿足V中任意2個相鄰頂點顏色不同，即將頂點集合劃分為q個獨立集。

2.1 相關定義

隨機圖理論作為圖論的重要分支，是由Erd?s等[5]在1959年引入隨機圖生成模型Gn,p而產生的。Gn,p模型中的參數n表示隨機圖的頂點個數，參數p表示隨機圖中任意2個頂點間以概率p相連。在該模型中，任意2個頂點之間是否存在邊的概率是獨立計算的，因此便于采用解析方法對其研究[6]。近幾十年，針對圖著色問題，研究人員已經從計算復雜性分析、色數、相變現象和求解算法等多個角度進行了大量的研究，并發現給定隨機圖的平均頂點度d=np，當d小于相變點Cs時，隨機圖高概率可著色，當d大于相變點Cs時，隨機圖高概率不可著色。

圖1為約束密度增大時幾類相變出現的位置以及解空間的變化情況。當頂點連通性很低時，所有解都出現在一個大解簇中，解與解的漢明距離很小，很容易從一個解“轉移”到另一個解；當連通性稍微增加時，解的相空間分解成指數級數量的簇。隨著約束密度的增加，解空間將依次經歷以下幾類不滿足相變。

Figure 1 The change trend of solution space of random constraint satisfaction problems with constraint density圖1 隨機約束滿足問題解空間隨約束密度的變化示意圖

2.2 隨機圖著色問題的不可滿足相變

2.2.1 聚類相變

當圖的頂點平均度達到相變點Cd時，隨機圖著色問題的解空間在結構上會發生變化，解空間的數目會突然增多，即解空間被分裂成數目眾多的子空間，每個子空間包含一定數目的解，但不同子空間的統計性質各不相同，且不同子空間解的相似度遠遠低于同一個子空間解的相似度。這一突變被稱為聚類相變，這個相變點Cd被稱為聚類相變點或動態轉移相變點。統計物理學認為聚類相變是由解簇上自旋變量之間的某些長程相關性引起的，這種相關性不是通常的兩點函數，而是點到集合的相關函數。2007年，Zdeborová等[12]得到隨機圖著色問題聚類相變點的漸進值，如式(1)所示：

Cd=k(lnq-ln lnq+1+o(1))

(1)

聚類相變也對應著一個信息理論問題的轉移，稱為樹重構相變點。Budzynski等[13]通過求解樹重構相變點得到了隨機圖著色問題聚類相變點新的漸進值，如式(2)所示：

Cd=qlnq+ln lnq+γd+o(1))

(2)

其中,γd=0.812，表1為q=3時，隨機圖著色問題的聚類相變點的研究成果。

Table 1 Clustering phase transition point of random coloring problem when q=3表1 3-隨機圖著色問題聚類相變點

2.2.2 冷凝相變

當約束密度超過Cd到達另一個相變點Cc時，隨機圖著色問題的解空間進一步變化，解空間的統計性質開始由那些包含微觀構型最多但是數目較少的子空間決定,此時解空間仍然有指數級數量的聚類解簇，并且這些聚類解簇之間彼此有較好的分離，這個變化現象被稱為冷凝相變。冷凝相變也是隨機約束滿足問題相變研究中的熱點。通過空腔法證實在可滿足相變點之前解空間會發生冷凝相變，標志著解空間幾何結構的進一步變化。冷凝現象似乎是解決各種問題的關鍵，包括尋找q色相變點和嚴格分析信息傳播算法。Zdeborová等[12]給出了隨機圖著色問題冷凝相變點的漸進值,如式(3)所示：

Cc=2qlnq-lnq-2 ln 2+o(1)

(3)

目前最好的冷凝相變點漸進值是Bapst等[18]給出的,如式(4)所示：

Cc=(2q-1)lnq-2 ln 2+εq

(4)

當q→∞時，εq→0。Bapst等[18]證明了在隨機圖著色問題中確實發生了冷凝相變，并且發生在空腔法預測的精確位置上。這也是第一個通過嚴格證明得到的隨機圖著色問題的冷凝相變點。

2.2.3 剛性相變

若約束密度超過變相點Cc，隨機圖著色問題的解空間將發生另一種重要的相變：有限部分的凍結變量出現在占優勢的解簇中時，剛性相變發生，這個相變點Cr被稱為剛性相變點。剛性相變點是動態相變點，剛性相變可能發生在冷凝相變之前，也可能發生在冷凝相變之后。Zdeborová等[12]首次分析了這種相變現象，并給出了隨機圖著色問題剛性相變點的漸進值，如式(5)所示：

Cr=q(lnq+ln lnq+1+o(1))

(5)

此后，Molloy[19]在文獻[12]的基礎上得到剛性相變點新的漸進值,如式(6)所示：

(6)

2.3 隨機圖著色問題的可滿足相變

隨機圖著色問題相變研究最多的是可滿足相變，但直接求解可滿足相變點是困難的，因此，研究人員通過對上下界的改進不斷逼近可著色相變點，并取得了一系列豐碩成果。2004年，Krz?kaa等[16]通過1RSB得到了隨機圖著色問題可著色相變點的下界，如式(7)所示：

Cs≥2qlnq-lnq-2+oq(1)

(7)

當q→∞時，oq(1)→0。與此同時，Achlioptas等[7]首次通過二階矩方法得到了隨機圖著色問題可著色相變點下界的漸進值,如式(8)所示：

2qlnq-2 lnq-2+oq(1)

(8)

2007年，Zdeborová 等[12]得到隨機圖著色問題可著色相變點的漸進值,如式(9)所示：

Cs=2qlnq-lnq-1+o(1)

(9)

Coja-Oghlan等[20]對可著色相變點下界的漸進值進一步改進得到式(10)：

Cc=2qlnq-lnq-2 ln 2

(10)

Cc為隨機圖著色問題的冷凝相變點，最早關于隨機圖著色問題可著色相變點上界的漸進值,如式(11)所示：

(11)

Coja-Oghlan[21]對可著色相變點上界的漸進值進一步改進得到式(12)：

(12)

可以觀察到上述文獻中相變點上下界的差值為2 ln 2-1+o(1)。相較于以往研究人員得到的可著色問題相變點上下界的差值會隨著q的增長不斷增大，2 ln 2-1+o(1)是目前可著色問題相變點上下界的最小差值。q=3的隨機圖著色相變點的研究進展，與q為任意值的時候有很大的聯系，但也有些區別。總體概括如表2所示。

Table 2 Coloring phase transition point of random coloring problem when q=3表2 3-隨機圖著色問題可著色相變點

3 隨機可滿足問題的相變

可滿足問題SAT(SATisfiability problem)是最具有代表意義的約束滿足問題。給定一個合取范式CNF(Conjunctive Normal Formula)F，本文用1和0表示隨機變元的true和false 。判定是否有一組布爾變元的指派真值指派x∈{0,1}n使F為真，這個判定問題就是SAT問題。長期以來SAT問題在人工智能和理論計算機科學中都是一個核心問題。

3.1 相關定義

每個子句長度均為k的SAT問題被稱為k-SAT問題，稱隨機k-SAT模型生成的實例為隨機k-SAT公式。雖然已經有很多性能優異的算法能夠求解變元規模很大的隨機k-SAT問題，但不論是完備求解算法還是非完備求解算法都仍有局限性。隨著約束密度不斷增大，這些算法會逐漸失效。這種現象激發了人們的研究興趣，研究人員揭示了計算復雜性與相變現象存在密切聯系，有學者認為NP-完全問題的相變研究是計算復雜性理論研究的延續，相變現象更直接、更細致地展示了約束滿足問題難解的本質。

3.2 隨機可滿足問題的不可滿足相變

在對隨機k-SAT問題的研究過程中，相變中解空間的變化與隨機k-SAT問題難解關系密切。由于統計物理學中對解空間結構分析的假設和方法的引入，對隨機k-SAT問題的不滿足相變的研究在近些年取得了很多突破性成果[23]。

3.2.1 聚類相變

3.2.2 冷凝相變

(13)

3.3 隨機可滿足問題的可滿足相變

(1)算法研究。

(14)

因為任意的SAT問題都能在多項式時間內規約到k-SAT問題，而隨機3-SAT問題是最簡單的NP-完全問題，因此對隨機3-SAT問題的相變研究具有特殊性和代表性，難解實例是在C3=4.25附近出現的，該相變點是基于回溯的DPLL算法的平均計算時間來刻畫的[30]。

研究人員發現可以通過算法實驗來得到相變點的下界。Crawford等[31]的研究結果表明,隨機3-SAT問題的數值實驗顯示相變點C3≈4.258。此后，Monasson等[32]通過實驗得到隨機3-SAT問題更新的相變點C3≈4.27。Mann等[33]通過“彈道網絡方法”克服了一般局部搜索算法容易陷入局部最優的問題，得到了C3≈4.267。對于隨機3-SAT問題的算法實驗表明相變點C3≈4.3。Kirkpatrick等[34]首次給出了k-SAT問題可滿足相變的相變點算法估計，運用完全算法估計方法得到C3≈4.17。

Chao等[35]通過設計算法一次一個地對文字進行賦值，直到找到一個解，或者發現進一步的賦值導致不能找到一個解。具體流程為：使用單位子句規則作為選擇下一個文字的啟發式策略，在每一步中，從包含最少數量文字的子句中隨機選擇一個文字進行賦值。進而求得隨機3-SAT問題可滿足相變點的下界為2.99。Chvátal等[36]將這一結果提升到2.67。Broder等[37]設計了基于純文字規則的啟發式算法,求得新的隨機3-SAT問題可滿足相變點的下界為1.63。此后，Frieze等[38]通過求解算法中的確切極限概率求得了新的下界為3.003，基于此，Achlioptas[39]在2000年提出了一種新的啟發式算法，并運用微分方程分析了算法,得到新的下界為3.145。之后Achlioptas等[40]又將下界的值提升到3.26。Kaporis等[41]設計了一種新的啟發式算法,得到新的隨機3-SAT問題可滿足相變點的下界為3.42。截止目前,隨機3-SAT問題可滿足相變點下界的最好結果是由Kaporis等[42]通過提出的一種啟發式算法得到的，該算法得到的相變點下界為3.52。當k=4時，Gent等[43]得到可滿足性相變點C4≈9.8。

本文中所提到的隨機3-SAT問題可滿足相變點下界的研究結果匯總如表3所示。

Table 3 Lower SAT/UNSAT threshold of random 3-SAT problem表3 隨機3-SAT問題可滿足相變點下界

(15)

由于NP問題的高度計算復雜性，在問題規模較大時，通過算法實驗和數值模擬的方法設計高效算法是困難的。因此，在算法實驗中估計出來的可滿足相變點，當問題規模較小時可能比較準確，當規模較大時估計值誤差較大。

(2)統計物理。

在統計物理學中,隨機k-SAT問題等效于隨機無序系統中的自旋玻璃，所以統計物理學在SAT問題的研究過程中表現相當活躍。對隨機k-SAT問題的研究可以納入到統計力學的研究框架中。下面從統計力學的角度綜述隨機k-SAT問題的研究成果。

通過統計物理學的有限尺寸縮放技術得到k=3,4,5,6時的可滿足相變點。在極限情況下，文獻[34]用一個簡單的概率給出了可滿足相變點的漸近表達式Cc?2kln 2。Monasson等[47]使用一階復本對稱方法對隨機k-SAT問題的可滿足變相點進行了研究，發現復本方法并不能有效求解此問題，Monasson得到的漸進相變點如式(16)所示：

(16)

Mézard等[48]將統計物理學的自旋玻璃模型引入隨機k-SAT問題的求解中，提出隨機k-SAT問題的解空間“存在多個狀態”，并利用統計物理學中的1RSB方法得到了隨機3-SAT問題的可滿足相變相變點為C3=4.256，并發現在可滿足相變點之前的某個位置解空間分裂成了指數級數量的解簇以及解簇的擴散這2種現象。而且他們認為隨機k-SAT問題難解的根本原因就是解空間分裂成指數級數量的小解簇。Mertens等[49]得到了隨機k-SAT問題的可滿足相變點是嚴格出現在幾類不滿足相變點之后的結論，這表明滿足/不可滿足相變點Cs始終處于穩定區域，且得到了可滿足相變點的漸進表達式,如式(17)所示：

(17)

目前的統計物理得到的最好估計值C3=4.262[50]。一段時間內，一些難解問題都通過統計物理學的方法得到了很好的解決，人們對約束滿足問題相變成因的認識也更為清晰。但是，隨著研究的深入，研究人員發現對于更多的隨機約束滿足問題，1RSB方法得到的相變點要比算法得到的極限點更小，因而研究人員開始重新考慮1RSB方法與求解問題難解性之間的關系。直至2007年，Zdeborov等[12]應用基于能量和熵觀點的landscape分析方法對解空間中占據主導地位的解簇進行了研究，推動了一系列對約束滿足問題相變現象的本質研究。隨著統計物理學在隨機約束滿足問題相變領域表現出強大生命力，產生了一系列重量級成果，以統計物理為核心研究技術的方向逐漸形成了一套比較完善的體系。但是，理論物理學對隨機k-SAT問題相變現象的大量研究成果都是基于物理學假設，因此其本身仍有一定的局限性。

(3)理論分析。

Franco等[51]在1983年利用最基本的一階矩方法首次給出了隨機3-SAT問題的上界為5.191，之后Maftouhi等[52]通過對一階矩進行改進得到了新的上界為5.081。Kamath等[53]運用球與箱子模型來生成隨機3-SAT實例并得到新的上界為4.758。Dubois等[54]得到隨機3-SAT新的上界為4.643。Kirousis等[55]通過CNF公式中一個隨機變量的遞減序列，得到了隨機3-SAT新的上界為4.602。Janson等[56]對文獻[51]中得到的所有真值賦值求和，這個和被重新表述為由n個點組成的自旋系統的配分函數，從而求得了隨機3-SAT新的上界為4.596。Kaporis等[57]將局部最大滿足真值分配方法與占用問題概率的結果相結合，求得了不滿足相變點小于4.571。Dubois等[58]通過提出一種新的矩方法得到了隨機3-SAT問題的上界為4.506。目前關于隨機3-SAT問題可滿足相變點最好的結果是4.484 9，是由Díaz等[59]使用概率方法得到的。

本文中所提到的隨機3-SAT問題可滿足相變點上界的研究結果匯總，如表4所示。

Table 4 Upper SAT/UNSAT threshold of random 3-SAT problem表4 隨機3-SAT問題可滿足相變點上界

對于任意k-SAT問題，Kaporis等[57]通過一階矩方法得到了隨機k-SAT問題可滿足相變點上界，如式(18)所示：

(18)

Achlioptas等[60]通過二階矩方法得到一個下界,如式(19)所示：

(19)

Achlioptas等[61]通過對二階矩方法進行改進，提出了一種新的加權方式,如式(20)所示：

(20)

其中,c表示隨機k-SAT問題對應的合取范式，u表示在賦值σ下文字被滿足的個數,λ>0。通過這種改進得到了新的相變點下界,如式(21)所示：

(21)

基于此，劉軍[62]提出了一種新的加權方法，如式(22)所示:

(22)

其中，β>-1,λ>0。

Coja-Oghlan等[63]得到了隨機k-SAT問題可滿足相變點新的下界,如式(23)所示：

(23)

之后，Coja-Oghlan等[64]得到隨機k-SAT問題新的上下界,如式(24)所示：

(24)

2015年，Ding等[65]突破性地證明了當k充分大時，可滿足相變點的正確性。證明存在一個常數k0，使得當k>k0時，隨機k-SAT存在精確相變現象，且有：

Cs(n)=2kln 2-(1+ln 2)/2+ok(1)

(25)

4 結束語

隨機圖著色問題和隨機可滿足問題相變研究已經取得了一系列突破性進展，但現階段并沒有得到問題的精確相變點,我們認為未來的研究重要圍繞以下幾點：

(1)設計更加高效的啟發式求解算法，得到更加精確的可滿足性相變點。

(2)通過高階復本對稱破壞平均場理論刻畫解空間結構，從而得到更加精確的可滿足性相變點。

隨機約束滿足問題的相變研究與問題難解之間有緊密的聯系，是理論計算機領域的重要課題之一。本文匯總了隨機圖著色問題和隨機可滿足問題的可滿足相變和不可滿足相變的國內外研究成果，并展望了未來的研究方向，以期對此領域相關的研究人員給予一定的幫助和啟迪。