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

(1.北方民族大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，寧夏 銀川 750021； 2.北方民族大學(xué)圖像圖形智能處理國(guó)家民委重點(diǎn)實(shí)驗(yàn)室，寧夏 銀川 750021)

1 引言

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

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

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

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

2 隨機(jī)圖著色的相變問(wèn)題

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

2.1 相關(guān)定義

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

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

Figure 1 The change trend of solution space of random constraint satisfaction problems with constraint density圖1 隨機(jī)約束滿(mǎn)足問(wèn)題解空間隨約束密度的變化示意圖

2.2 隨機(jī)圖著色問(wèn)題的不可滿(mǎn)足相變

2.2.1 聚類(lèi)相變

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

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

(1)

聚類(lèi)相變也對(duì)應(yīng)著一個(gè)信息理論問(wèn)題的轉(zhuǎn)移，稱(chēng)為樹(shù)重構(gòu)相變點(diǎn)。Budzynski等[13]通過(guò)求解樹(shù)重構(gòu)相變點(diǎn)得到了隨機(jī)圖著色問(wèn)題聚類(lèi)相變點(diǎn)新的漸進(jìn)值，如式(2)所示：

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

(2)

其中,γd=0.812，表1為q=3時(shí)，隨機(jī)圖著色問(wèn)題的聚類(lèi)相變點(diǎn)的研究成果。

Table 1 Clustering phase transition point of random coloring problem when q=3表1 3-隨機(jī)圖著色問(wèn)題聚類(lèi)相變點(diǎn)

2.2.2 冷凝相變

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

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

(3)

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

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

(4)

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

2.2.3 剛性相變

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

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

(5)

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

(6)

2.3 隨機(jī)圖著色問(wèn)題的可滿(mǎn)足相變

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

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

(7)

當(dāng)q→∞時(shí)，oq(1)→0。與此同時(shí)，Achlioptas等[7]首次通過(guò)二階矩方法得到了隨機(jī)圖著色問(wèn)題可著色相變點(diǎn)下界的漸進(jìn)值,如式(8)所示：

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

(8)

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

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

(9)

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

Cc=2qlnq-lnq-2 ln 2

(10)

Cc為隨機(jī)圖著色問(wèn)題的冷凝相變點(diǎn)，最早關(guān)于隨機(jī)圖著色問(wèn)題可著色相變點(diǎn)上界的漸進(jìn)值,如式(11)所示：

(11)

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

(12)

可以觀(guān)察到上述文獻(xiàn)中相變點(diǎn)上下界的差值為2 ln 2-1+o(1)。相較于以往研究人員得到的可著色問(wèn)題相變點(diǎn)上下界的差值會(huì)隨著q的增長(zhǎng)不斷增大，2 ln 2-1+o(1)是目前可著色問(wèn)題相變點(diǎn)上下界的最小差值。q=3的隨機(jī)圖著色相變點(diǎn)的研究進(jìn)展，與q為任意值的時(shí)候有很大的聯(lián)系，但也有些區(qū)別?？傮w概括如表2所示。

Table 2 Coloring phase transition point of random coloring problem when q=3表2 3-隨機(jī)圖著色問(wèn)題可著色相變點(diǎn)

3 隨機(jī)可滿(mǎn)足問(wèn)題的相變

可滿(mǎn)足問(wèn)題SAT(SATisfiability problem)是最具有代表意義的約束滿(mǎn)足問(wèn)題。給定一個(gè)合取范式CNF(Conjunctive Normal Formula)F，本文用1和0表示隨機(jī)變?cè)膖rue和false 。判定是否有一組布爾變?cè)闹概烧嬷抵概蓌∈{0,1}n使F為真，這個(gè)判定問(wèn)題就是SAT問(wèn)題。長(zhǎng)期以來(lái)SAT問(wèn)題在人工智能和理論計(jì)算機(jī)科學(xué)中都是一個(gè)核心問(wèn)題。

3.1 相關(guān)定義

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

3.2 隨機(jī)可滿(mǎn)足問(wèn)題的不可滿(mǎn)足相變

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

3.2.1 聚類(lèi)相變

3.2.2 冷凝相變

(13)

3.3 隨機(jī)可滿(mǎn)足問(wèn)題的可滿(mǎn)足相變

(1)算法研究。

(14)

因?yàn)槿我獾腟AT問(wèn)題都能在多項(xiàng)式時(shí)間內(nèi)規(guī)約到k-SAT問(wèn)題，而隨機(jī)3-SAT問(wèn)題是最簡(jiǎn)單的NP-完全問(wèn)題，因此對(duì)隨機(jī)3-SAT問(wèn)題的相變研究具有特殊性和代表性，難解實(shí)例是在C3=4.25附近出現(xiàn)的，該相變點(diǎn)是基于回溯的DPLL算法的平均計(jì)算時(shí)間來(lái)刻畫(huà)的[30]。

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

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

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

Table 3 Lower SAT/UNSAT threshold of random 3-SAT problem表3 隨機(jī)3-SAT問(wèn)題可滿(mǎn)足相變點(diǎn)下界

(15)

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

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

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

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

(16)

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

(17)

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

(3)理論分析。

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

本文中所提到的隨機(jī)3-SAT問(wèn)題可滿(mǎn)足相變點(diǎn)上界的研究結(jié)果匯總，如表4所示。

Table 4 Upper SAT/UNSAT threshold of random 3-SAT problem表4 隨機(jī)3-SAT問(wèn)題可滿(mǎn)足相變點(diǎn)上界

對(duì)于任意k-SAT問(wèn)題，Kaporis等[57]通過(guò)一階矩方法得到了隨機(jī)k-SAT問(wèn)題可滿(mǎn)足相變點(diǎn)上界，如式(18)所示：

(18)

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

(19)

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

(20)

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

(21)

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

(22)

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

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

(23)

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

(24)

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

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

(25)

4 結(jié)束語(yǔ)

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

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

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

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