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

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

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

1 引言

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

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

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

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

2 隨機圖著色的相變問題

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

2.1 相關(guān)定義

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

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

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

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

2.2.1 聚類相變

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

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

(1)

聚類相變也對應(yīng)著一個信息理論問題的轉(zhuǎn)移，稱為樹重構(gòu)相變點。Budzynski等[13]通過求解樹重構(gòu)相變點得到了隨機圖著色問題聚類相變點新的漸進值，如式(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 冷凝相變

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

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

(3)

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

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

(4)

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

2.2.3 剛性相變

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

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

(5)

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

(6)

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

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

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

(7)

當(dāng)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為隨機圖著色問題的冷凝相變點，最早關(guān)于隨機圖著色問題可著色相變點上界的漸進值,如式(11)所示：

(11)

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

(12)

可以觀察到上述文獻中相變點上下界的差值為2 ln 2-1+o(1)。相較于以往研究人員得到的可著色問題相變點上下界的差值會隨著q的增長不斷增大，2 ln 2-1+o(1)是目前可著色問題相變點上下界的最小差值。q=3的隨機圖著色相變點的研究進展，與q為任意值的時候有很大的聯(lián)系，但也有些區(qū)別?？傮w概括如表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問題在人工智能和理論計算機科學(xué)中都是一個核心問題。

3.1 相關(guān)定義

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

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

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

3.2.1 聚類相變

3.2.2 冷凝相變

(13)

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

(1)算法研究。

(14)

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

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

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

本文中所提到的隨機3-SAT問題可滿足相變點下界的研究結(jié)果匯總?cè)绫?所示。

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

(15)

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

(2)統(tǒng)計物理。

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

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

(16)

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

(17)

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

(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個點組成的自旋系統(tǒng)的配分函數(shù)，從而求得了隨機3-SAT新的上界為4.596。Kaporis等[57]將局部最大滿足真值分配方法與占用問題概率的結(jié)果相結(jié)合，求得了不滿足相變點小于4.571。Dubois等[58]通過提出一種新的矩方法得到了隨機3-SAT問題的上界為4.506。目前關(guān)于隨機3-SAT問題可滿足相變點最好的結(jié)果是4.484 9，是由Díaz等[59]使用概率方法得到的。

本文中所提到的隨機3-SAT問題可滿足相變點上界的研究結(jié)果匯總，如表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]通過對二階矩方法進行改進，提出了一種新的加權(quán)方式,如式(20)所示：

(20)

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

(21)

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

(22)

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

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

(23)

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

(24)

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

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

(25)

4 結(jié)束語

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

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

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

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