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

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

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

【學位級別】：碩士

【部分圖文】：

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

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

上式表明撇和K滿足線性關系。對K求二階偏導數(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ù)足線性關系。其中，兄是2一子句3一子句的當量，它的直觀含義是指統(tǒng)計意義下，一個2一子句有相當于兄個3一子句的約束能力。下圖是變量數(shù)等于100的大量2一3一SAT實例相變點的統(tǒng)計結果。圖中顯示的可滿足概率等于0.63的等值線，x軸表示相變點處的2一子句數(shù)目，軸表示相變點處的3一子句數(shù)目。從圖中可以看出很好的線性，斜率大為一3.13，和我們理論上的預測非常接近。

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



本文編號：3262208