本文關(guān)鍵詞：人工智能視野下的進(jìn)化邏輯研究，由筆耕文化傳播整理發(fā)布。

《中國科學(xué)院研究生院（計(jì)算技術(shù)研究所）》 1997年

命題邏輯的可滿足性問題：復(fù)雜性和算法

卜東波  

【摘要】：可滿足性問題(Satisfiablity問題)在數(shù)理邏輯、人工智能、機(jī)器學(xué)習(xí)、約束滿足問題、VLSI集成電路設(shè)計(jì)與檢測以及計(jì)算機(jī)科學(xué)理論等等領(lǐng)域具有廣闊的應(yīng)用背景�？蓾M足性問題是第一個(gè)NP-Complete問題，并且是一大類NP-Complete問題的核心。大量的實(shí)踐表明，，許多NP-Complete問題無論是對(duì)于計(jì)算機(jī)科學(xué)理論還是工程應(yīng)用都有著至關(guān)重要的意義�？蓾M足性問題的重要性以及它的一些奇妙的性質(zhì)促使我們從問題和算法兩個(gè)角度來研究它。 我們主要從問題本身的固有性質(zhì)和快速求解算法兩個(gè)角度來研究可滿足性問題。值得注意的是：這兩方面的研究工作是相輔相成、互相促進(jìn)、互相啟發(fā)的。從問題的角度，我們著重研究可滿足性問題的相變現(xiàn)象以及問題實(shí)例的難度。這方面的工作更加清晰地刻劃出問題本身的固有屬性，從而有助于對(duì)問題的完整認(rèn)識(shí)和合理分類，并且針對(duì)于各個(gè)不同的問題子類可以開發(fā)出更有效的算法。從算法的角度，我們分析了完備性算法和不完備性算法的復(fù)雜性，比較了兩者的優(yōu)缺點(diǎn)和適用范圍，進(jìn)而提出了將以上兩種算法更加完美的結(jié)合的思想。我們提出的算法CCSAT和USAT，即分別針對(duì)于利用不完備性算法為完備性算法提供更強(qiáng)的啟發(fā)式信息和利用完備性算法幫助不完備性算法處理局部極值點(diǎn)兩個(gè)方向的結(jié)合。通過重新認(rèn)識(shí)2SAT∈P這一結(jié)論證明的實(shí)質(zhì)，也給算法的設(shè)計(jì)提供了新的思路。 問題的復(fù)雜性是問題的一個(gè)固有屬性。我們?cè)噲D用難度這個(gè)概念來描述和刻劃它，并且給出了難度的一個(gè)新的、形式化定義的猜想。自然界中的物質(zhì)皆有其物態(tài)和相，以及隨系統(tǒng)序參數(shù)而發(fā)生的物質(zhì)從一個(gè)相到另一個(gè)相的相變現(xiàn)象。作為一個(gè)復(fù)雜的計(jì)算系統(tǒng)，可滿足性問題也有一個(gè)奇妙的相變現(xiàn)象，即問題實(shí)例的可滿足概率隨著實(shí)例的特定序參量的變化而發(fā)生的突變現(xiàn)象。我們提出了一種布爾篩模型，更加清晰地描述出相變現(xiàn)象。 我們主要做了以下8項(xiàng)工作，分為問題性質(zhì)剖析類(標(biāo)記為“P”)和

【關(guān)鍵詞】：
【學(xué)位授予單位】：中國科學(xué)院研究生院（計(jì)算技術(shù)研究所）
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：1997
【分類號(hào)】：TP18
【目錄】：

摘要4-7

Abstract7-12

第一章 引言12-16

1.1 NP-Complete問題和可滿足性問題12-13

1.2 算法的優(yōu)劣：收斂性和復(fù)雜性13-14

1.3 論文概要14-16

第二章 可滿足性問題綜述16-32

2.1 可滿足問題的表示16-17

2.2 求解SAT問題的算法17-27

2.2.1 完備性算法18-23

2.2.2 局部搜索算法(Local Search)23-27

2.3 相變現(xiàn)象27-32

2.3.1 物理學(xué)中的相變現(xiàn)象27-30

2.3.2 可滿足性問題中的相變現(xiàn)象30-32

第三章 相變現(xiàn)象和難度32-48

3.1 3-SAT問題可滿足概率的布爾篩模型32-37

3.2 2-3-SAT問題的可滿足概率37-39

3.3 相變現(xiàn)象的統(tǒng)計(jì)描述39-45

3.3.1 可能解的個(gè)數(shù)的期望值39-44

3.3.2 相變點(diǎn)上界的估計(jì)44-45

3.4.總結(jié)45

3.5 進(jìn)一步的討論45-48

第四章 可滿足性問題的求解算法48-67

4.1 完備性算法和不完備性算法的比較48-49

4.2 求解SAT問題的完備性算法—CCSAT(Conflicted Cycle SAT)49-55

4.2.1 Crawford方案的剖析和CCSAT算法的提出49-52

4.2.2 mom策略的缺陷52-53

4.2.3 無級(jí)重排53-54

4.2.4.實(shí)驗(yàn)數(shù)據(jù)54-55

4.3 求解SAT問題算法的統(tǒng)一模型USAT(Uniform SAT)55-60

4.3.1 GSAT算法的特點(diǎn)及子空間旋轉(zhuǎn)策略的引入55-56

4.3.2 統(tǒng)一的算法模型USAT56-58

4.3.3 實(shí)驗(yàn)數(shù)據(jù)58-59

4.3.4 總結(jié)59-60

4.4 求解SAT問題的第三類算法—概率性算法60-62

4.5 完備性算法APTSAT(Avoid Phase Transition SAT)62-64

4.5.1 子問題的又一種分類方法63

4.5.2 完備性算法APTSAT63-64

4.6 新的剪枝規(guī)則：Subset-Prune剪枝64-67

4.6.1 求解2-SAT問題的P算法64-66

4.6.2 Subset-Prune剪枝規(guī)則66-67

第五章 結(jié)束語67-68

參考文獻(xiàn)68-71

碩士期間發(fā)表的論文71-72

作者簡歷72

下載全文 更多同類文獻(xiàn)

CAJ全文下載

(如何獲取全文？ 歡迎：購買知網(wǎng)充值卡、在線充值、在線咨詢)

CAJViewer閱讀器支持CAJ、PDF文件格式

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前3條

1 李未,黃文奇;一種求解合取范式可滿足性問題的數(shù)學(xué)物理方法[J];中國科學(xué)(A輯 數(shù)學(xué) 物理學(xué) 天文學(xué) 技術(shù)科學(xué));1994年11期

2 黃文奇,金人超;求解SAT問題的擬物擬人算法—Solar[J];中國科學(xué)E輯:技術(shù)科學(xué);1997年02期

3 白碩,卜東波;2-3-SAT問題相變現(xiàn)象剖析及其應(yīng)用[J];軟件學(xué)報(bào);1998年11期

【共引文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 張曉君;;為什么語言學(xué)研究離不開邏輯學(xué)——2009語言學(xué)和邏輯學(xué)交叉研究研討會(huì)側(cè)記[J];畢節(jié)學(xué)院學(xué)報(bào);2010年05期

2 劉云翔,孫吉貴;模糊集合的語義[J];長春工程學(xué)院學(xué)報(bào)(自然科學(xué)版);2003年03期

3 鄧安生,關(guān)偉洲;布爾算子模糊邏輯中的廣義半鎖歸結(jié)原理[J];東北師大學(xué)報(bào)(自然科學(xué)版);2000年03期

4 鄧安生;布爾算子模糊邏輯中的刪除策略[J];東北師大學(xué)報(bào)(自然科學(xué)版);1998年01期

5 胡勤;;人工智能概述[J];電腦知識(shí)與技術(shù);2010年13期

6 劉富春;;再擴(kuò)充模糊邏輯中歸結(jié)方法的有效性[J];廣東工業(yè)大學(xué)學(xué)報(bào);2006年01期

7 鄧蘇,張維明,陳文偉,陳衛(wèi)東,湯大權(quán);軟試驗(yàn)床關(guān)鍵技術(shù)——知識(shí)獲取及管理系統(tǒng)[J];國防科技參考;1995年01期

8 滕至陽,袁全生,程正潮;分割圖描述的正確性驗(yàn)證[J];高技術(shù)通訊;1998年04期

9 趙天玉;組合優(yōu)化算法中擺脫局部極小值的幾種策略[J];工科數(shù)學(xué);2000年01期

10 萬良;;隨機(jī)填充問題與排課系統(tǒng)[J];貴州教育學(xué)院學(xué)報(bào);2007年02期

中國重要會(huì)議論文全文數(shù)據(jù)庫 前3條

1 黃文奇;陳端兵;;用純粹擬人型算法求解超大規(guī)模集成電路布局中的矩形packing問題[A];2005年全國理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會(huì)論文集[C];2005年

2 賴家俊;潘小東;徐開俊;徐揚(yáng);;基于十八元非鏈格值命題邏輯L_(18)P(X)中的歸結(jié)方法的研究[A];第六屆中國不確定系統(tǒng)年會(huì)論文集[C];2008年

3 于津;劉敘華;;基于不確定、不精確知識(shí)的推理系統(tǒng)-UKRS[A];1996年中國智能自動(dòng)化學(xué)術(shù)會(huì)議論文集（上冊(cè)）[C];1996年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 周俊萍;自動(dòng)推理與規(guī)劃問題最小上界和相變規(guī)律研究[D];吉林大學(xué);2011年

2 胡明娣;邏輯度量空間的內(nèi)蘊(yùn)結(jié)構(gòu)的研究[D];陜西師范大學(xué);2011年

3 鄒麗;基于語言真值格蘊(yùn)涵代數(shù)的格值命題邏輯及其歸結(jié)自動(dòng)推理研究[D];西南交通大學(xué);2010年

4 熊正大;鏈?zhǔn)綆缀谓Y(jié)構(gòu)的擬人型優(yōu)化方法[D];華中科技大學(xué);2011年

5 黃越;數(shù)字集成電路自動(dòng)測試生成算法研究[D];江南大學(xué);2012年

6 趙孝武;求解正交表問題的擬物擬人方法[D];中國科學(xué)院軟件研究所;2001年

7 趙光峰;格蘊(yùn)涵代數(shù)與圖的升分解問題的研究[D];西南交通大學(xué);2002年

8 馬駿;基于格蘊(yùn)涵代數(shù)的格值邏輯系統(tǒng)及其自動(dòng)推理的研究[D];西南交通大學(xué);2002年

9 斐崢;基于神經(jīng)網(wǎng)絡(luò)的自動(dòng)推理理論及方法的研究[D];西南交通大學(xué);2002年

10 湯永川;關(guān)于不確定性推理理論與知識(shí)發(fā)現(xiàn)的研究[D];西南交通大學(xué);2002年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 劉文赫;Horn子句型信念的靜態(tài)非修正處理方法研究[D];大連海事大學(xué);2011年

2 周國城;求解圓形Packing問題及模型蛋白結(jié)構(gòu)預(yù)測問題的啟發(fā)式算法[D];南京信息工程大學(xué);2011年

3 陳穩(wěn);基于DPLL的SAT算法的研究及應(yīng)用[D];電子科技大學(xué);2011年

4 金宏妍;人工智能視野下的進(jìn)化邏輯研究[D];燕山大學(xué);2010年

5 倪海文;團(tuán)簇基態(tài)結(jié)構(gòu)預(yù)測的高效啟發(fā)式算法[D];華中科技大學(xué);2011年

6 黃沖;組合優(yōu)化中的命題邏輯[D];華中科技大學(xué);2011年

7 汪軻;無線傳感網(wǎng)絡(luò)覆蓋控制策略的研究[D];浙江師范大學(xué);2011年

8 吳瑕;布爾算子模糊邏輯中的調(diào)解法[D];東北師范大學(xué);2002年

9 高燕;基于數(shù)據(jù)挖掘技術(shù)的海關(guān)執(zhí)法評(píng)估系統(tǒng)的研究與開發(fā)[D];武漢理工大學(xué);2002年

10 王宏川;因果圖推理及其應(yīng)用研究[D];重慶大學(xué);2002年

【二級(jí)參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前6條

1 黃文奇,陳亮;求解有關(guān)空間利用的調(diào)度問題的擬物方法[J];中國科學(xué)(A輯 數(shù)學(xué) 物理學(xué) 天文學(xué) 技術(shù)科學(xué));1991年03期

2 李未;一個(gè)開放的邏輯系統(tǒng)[J];中國科學(xué)(A輯 數(shù)學(xué) 物理學(xué) 天文學(xué) 技術(shù)科學(xué));1992年10期

3 李未,黃文奇;一種求解合取范式可滿足性問題的數(shù)學(xué)物理方法[J];中國科學(xué)(A輯 數(shù)學(xué) 物理學(xué) 天文學(xué) 技術(shù)科學(xué));1994年11期

4 黃文奇;求解Covering問題的擬物方法——NP難度問題的一個(gè)處理途徑[J];計(jì)算機(jī)學(xué)報(bào);1989年08期

5 黃文奇,朱虹,許向陽,宋益民;求解方格packing問題的啟發(fā)式算法[J];計(jì)算機(jī)學(xué)報(bào);1993年11期

6 黃文奇,詹叔浩;求解Packing問題的擬物方法[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);1979年02期

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 徐小萍;;MARG-MU(2)的結(jié)構(gòu)和復(fù)雜度[J];井岡山學(xué)院學(xué)報(bào);2009年02期

2 張德富;求解難可滿足性問題的混合算法[J];小型微型計(jì)算機(jī)系統(tǒng);2003年08期

3 丁敏;唐璞山;;改進(jìn)的時(shí)間幀展開的時(shí)序電路等價(jià)驗(yàn)證算法[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2006年01期

4 張忠林;唐璞山;;一個(gè)基于可滿足性算法的時(shí)序深度計(jì)算方法[J];計(jì)算機(jī)工程;2006年02期

5 蘇俊霞;;社會(huì)認(rèn)識(shí)優(yōu)化在非線性規(guī)劃問題中的應(yīng)用[J];計(jì)算機(jī)仿真;2007年09期

6 畢忠勤;陳光喜;單美靜;;可滿足性問題全部解的求解算法[J];計(jì)算機(jī)工程與應(yīng)用;2009年03期

7 王建新;管利娜;江國紅;;可滿足性問題的研究綜述[J];計(jì)算技術(shù)與自動(dòng)化;2009年04期

8 吳耀輝;梁豐;蔡宇;;基于SystemC的SAT求解器設(shè)計(jì)[J];電腦知識(shí)與技術(shù);2010年14期

9 余豐人;丘海明;;關(guān)于合取范式可滿足性問題的復(fù)雜性分析[J];中山大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年02期

10 荊明娥;陳更生;趙長虹;唐璞山;周電;;利用正交方法解SAT問題[J];復(fù)旦學(xué)報(bào)(自然科學(xué)版);2008年06期

中國重要會(huì)議論文全文數(shù)據(jù)庫 前1條

1 熊偉;唐璞山;;一種新的SAT問題預(yù)處理算法[A];2007年全國開放式分布與并行計(jì)算機(jī)學(xué)術(shù)會(huì)議論文集(下冊(cè))[C];2007年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 丁敏;可滿足性問題算法研究以及在時(shí)序電路等價(jià)驗(yàn)證中的應(yīng)用[D];復(fù)旦大學(xué);2005年

2 楊軍;集成電路的邏輯等價(jià)性驗(yàn)證研究[D];浙江大學(xué);2007年

3 翁延玲;RTL到門級(jí)設(shè)計(jì)的等價(jià)性驗(yàn)證的研究[D];浙江大學(xué);2008年

4 沈靜;約束滿足問題的模型構(gòu)造和相變現(xiàn)象[D];華中師范大學(xué);2011年

5 鄭飛君;基于布爾可滿足性的邏輯電路等價(jià)性驗(yàn)證和測試生成技術(shù)研究[D];浙江大學(xué);2008年

6 許有軍;基于擴(kuò)展規(guī)則的若干SAT問題研究[D];吉林大學(xué);2011年

7 張立明;結(jié)合可滿足的基于模型等價(jià)性驗(yàn)證及不一致診斷問題研究[D];吉林大學(xué);2012年

8 曾國強(qiáng);改進(jìn)的極值優(yōu)化算法及其在組合優(yōu)化問題中的應(yīng)用研究[D];浙江大學(xué);2011年

9 汪雋;受生物啟發(fā)的脈沖神經(jīng)膜系統(tǒng)的計(jì)算能力研究[D];華中科技大學(xué);2013年

10 黃玉芳;算法Tile自組裝系統(tǒng)的設(shè)計(jì)與應(yīng)用研究[D];華中科技大學(xué);2010年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 江智蘭;DNA計(jì)算模型研究與探索[D];安徽理工大學(xué);2013年

2 王霄維;應(yīng)用于集成電路形式化驗(yàn)證的SAT算法研究[D];長春工業(yè)大學(xué);2010年

3 傅琳璐;基于分支回溯的NAE-3SAT及#NAE-3SAT問題求解算法[D];東北師范大學(xué);2013年

4 宋勃升;DNA自組裝計(jì)算模型的應(yīng)用研究[D];安徽理工大學(xué);2011年

5 黃勁楠;可滿足性問題算法研究-CNF的簡化[D];復(fù)旦大學(xué);2008年

6 姚堯;基于回歸分析和DCM模型的可滿足性問題求解算法[D];東華大學(xué);2011年

7 趙松云;基于子句權(quán)重求解SAT問題[D];復(fù)旦大學(xué);2008年

8 趙偉楠;對(duì)可滿足性（SAT）問題求全解的算法研究及實(shí)現(xiàn)[D];北京交通大學(xué);2009年

9 王全新;量子進(jìn)化算法改進(jìn)及應(yīng)用研究[D];吉林大學(xué);2007年

10 陳穩(wěn);基于DPLL的SAT算法的研究及應(yīng)用[D];電子科技大學(xué);2011年

  本文關(guān)鍵詞：人工智能視野下的進(jìn)化邏輯研究，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：66062