可滿足性問題（Satisfiablity問題）在數(shù)理邏輯、人工智能、機(jī)器學(xué)習(xí)、約束滿足問題、VLSI集成電路設(shè)計與檢測以及計算機(jī)科學(xué)理論等等領(lǐng)域具有廣闊的應(yīng)用背景�？蓾M足性問題是第一個NP-Complete問題，并且是一大類NP-Complete問題的核心。大量的實踐表明，許多NP-Complete問題無論是對于計算機(jī)科學(xué)理論還是工程應(yīng)用都有著至關(guān)重要的意義�？蓾M足性問題的重要性以及它的一些奇妙的性質(zhì)促使我們從問題和算法兩個角度來研究它。 我們主要從問題本身的固有性質(zhì)和快速求解算法兩個角度來研究可滿足性問題。值得注意的是：這兩方面的研究工作是相輔相成、互相促進(jìn)、互相啟發(fā)的。從問題的角度，我們著重研究可滿足性問題的相變現(xiàn)象以及問題實例的難度。這方面的工作更加清晰地刻劃出問題本身的固有屬性，從而有助于對問題的完整認(rèn)識和合理分類，并且針對于各個不同的問題子類可以開發(fā)出更有效的算法。從算法的角度，我們分析了完備性算法和不完備性算法的復(fù)雜性，比較了兩者的優(yōu)缺點和適用范圍，進(jìn)而提出了將以上兩種算法更加完美的結(jié)合的思想。我們提出的算法CCSAT和USAT，即分別針對于利用不完備性算法為完備性算... 

【文章來源】：中國科學(xué)院大學(xué)(中國科學(xué)院計算技術(shù)研究所)北京市

【文章頁數(shù)】：72 頁

【學(xué)位級別】：碩士

【部分圖文】：

2.13一AT問題的相變曲線和難度曲線

當(dāng)問題規(guī)模稍大以后，相變曲線就變得非常陡峭，可滿足概0.63的點和等于0.5的點靠得非常近，實驗記錄對這兩點難度的不能做到十分得顯著，于是這微小的差異常常被不足夠精細(xì)的實略。但是，仍有一些工作發(fā)現(xiàn)了一個奇異的現(xiàn)象，即隨著問題規(guī)加會觀察到“傳統(tǒng)”相變點(即Pr(c入，，=TRUE)=.05的點)向的現(xiàn)象。利用上述結(jié)果可以對相變點的向左漂移現(xiàn)象給出初步的解釋。表中可以看出我們估計的相變點基本穩(wěn)定在4.21處，因而可以足概率等于(l一1/e)的點看作一個樞軸，隨著問題規(guī)模的增加，概率曲線慢慢轉(zhuǎn)動，變得越來越陡峭，結(jié)果導(dǎo)致“傳統(tǒng)”的相變向左漂移。下圖是0.DuboiS針對不同的問題規(guī)模測得相變曲線數(shù)據(jù)〔v]l，從圖中可以清楚地看出不同規(guī)模的相變曲線有一個交點，這個交點不是位于可滿足概率等于0.5的地方，而是明顯地高于且“傳統(tǒng)”的相變點有明顯的左漂移現(xiàn)象。

上式表明撇和K滿足線性關(guān)系。對K求二階偏導(dǎo)數(shù)可以得到同樣的論。2一SAT和3一SAT可以視為2一3一SAT的兩個特例，因而也必定滿足(2)，將2一SAT和3一SAT的相變點作為特殊解代入式(2)，可得:K+加M=P0*N成立。其中:;=’go況g。3二.312……定理3.2.2表明2一3一SAT的相變點處的2一子句個數(shù)和3一子句個數(shù)足線性關(guān)系。其中，兄是2一子句3一子句的當(dāng)量，它的直觀含義是指統(tǒng)計意義下，一個2一子句有相當(dāng)于兄個3一子句的約束能力。下圖是變量數(shù)等于100的大量2一3一SAT實例相變點的統(tǒng)計結(jié)果。圖中顯示的可滿足概率等于0.63的等值線，x軸表示相變點處的2一子句數(shù)目，軸表示相變點處的3一子句數(shù)目。從圖中可以看出很好的線性，斜率大為一3.13，和我們理論上的預(yù)測非常接近。

【參考文獻(xiàn)】：
期刊論文
[1]2-3-SAT問題相變現(xiàn)象剖析及其應(yīng)用[J]. 白碩,卜東波.  軟件學(xué)報. 1998(11)
[2]求解SAT問題的擬物擬人算法—Solar[J]. 黃文奇,金人超.  中國科學(xué)E輯:技術(shù)科學(xué). 1997(02)
[3]一種求解合取范式可滿足性問題的數(shù)學(xué)物理方法[J]. 李未,黃文奇.  中國科學(xué)（A輯 數(shù)學(xué) 物理學(xué) 天文學(xué) 技術(shù)科學(xué)）. 1994(11)



本文編號：3262208