本文關(guān)鍵詞：命題邏輯中隨機(jī)3-SAT問題算法研究，由筆耕文化傳播整理發(fā)布。

【摘要】：命題邏輯公式的可滿足性問題(SAT)是計(jì)算機(jī)科學(xué)和人工智能中一個(gè)重要問題。它是第一個(gè)被證明了的NP完全問題,由Stephen Cook于1971年提出。SAT問題在人工智能、軟件工程、VLSI集成電路設(shè)計(jì)等領(lǐng)域具有廣泛的應(yīng)用。3-SAT問題是每個(gè)子句的文字個(gè)數(shù)固定為3的SAT問題。作為SAT問題的子問題之一,3-SAT問題也是NP完全問題。3-SAT問題有來自工業(yè)問題轉(zhuǎn)化的實(shí)際問題,也有機(jī)器自動(dòng)生成的。來自工業(yè)問題轉(zhuǎn)化的3-SAT問題在數(shù)目和結(jié)構(gòu)上都有很大的限制,根本不能滿足各類SAT算法的測(cè)試需求,所以目前大部分的3-SAT問題來自機(jī)器自動(dòng)生成,這類問題又稱為隨機(jī)3-SAT問題。當(dāng)變?cè)臄?shù)目達(dá)到1000乃至1兆的規(guī)模時(shí),3-SAT問題的求解變得異常困難,所以對(duì)大規(guī)模隨機(jī)3-SAT的求解是一個(gè)比較有前景的研究領(lǐng)域。自從20世紀(jì)80年代隨機(jī)3-SAT問題被提出以來,很多學(xué)者在這方面做了大量的工作,提出了各種各樣的算法。當(dāng)前較為高效的算法有Sparrow2011算法、ProbSAT算法、CCMC算法等。然而這些算法,在求解較大規(guī)模的隨機(jī)3-SAT問題上的效率仍不夠理想。本文在綜合分析以往SAT問題算法的基礎(chǔ)上,在提高隨機(jī)3-SAT問題的求解效率方面主要做了如下工作：1、基于SAT問題的自身結(jié)構(gòu),研究各個(gè)文字在子句集中出現(xiàn)的頻率,挖掘出文字與子句集可滿足性判定的關(guān)系。給出文字的關(guān)鍵度和關(guān)鍵文字的概念,利用關(guān)鍵文字規(guī)則和DPLL規(guī)則設(shè)計(jì)出了對(duì)子句集初始真值指派的優(yōu)化策略。2、給出了基于優(yōu)化后的初始真值指派的新的WASAT算法,算法先是運(yùn)用真值指派綜合評(píng)估函數(shù)來尋求更優(yōu)的賦值,然后運(yùn)用子句權(quán)重重置的策略,跳出局部最優(yōu)解開辟新的搜索區(qū)域。3、運(yùn)用來自SAT競(jìng)賽網(wǎng)站的不同規(guī)模的隨機(jī)3-SAT實(shí)例設(shè)計(jì)實(shí)驗(yàn)并得出結(jié)果。通過對(duì)比Sparrow2011算法、ProbSAT算法、CCMC算法,評(píng)估并分析了新的權(quán)重分析算法的效率。
【關(guān)鍵詞】：子句 子句集 隨機(jī)3-SAT 可滿足性 關(guān)鍵文字 子句權(quán)重 真值指派 權(quán)重重置 權(quán)值評(píng)估函數(shù)
【學(xué)位授予單位】：西南交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O141
【目錄】：

• 摘要6-8
• Abstract8-12
• 第1章 緒論12-17
• 1.1 研究背景和和研究意義12-13
• 1.2 國內(nèi)外研究現(xiàn)狀13-15
• 1.3 本文研究的內(nèi)容和結(jié)構(gòu)安排15-17
• 第2章 基礎(chǔ)知識(shí)17-21
• 2.1 基本概念17-19
• 2.2 符號(hào)說明19-20
• 2.3 本章小結(jié)20-21
• 第3章 4種SAT問題的算法介紹21-29
• 3.1 SDF算法21-23
• 3.2 Sparrow2011算法23-25
• 3.3 ProbSAT算法25-26
• 3.4 CCMC算法26-27
• 3.5 本章小結(jié)27-29
• 第4章 隨機(jī)3-SAT問題新算法29-46
• 4.1 初始賦值的優(yōu)化29-37
• 4.2 隨機(jī)3-SAT問題新算法37-40
• 4.3 子句權(quán)重重置函數(shù)40-45
• 4.4 本章小結(jié)45-46
• 第5章 算法評(píng)估46-51
• 5.1 理論評(píng)估46-47
• 5.2 測(cè)試標(biāo)準(zhǔn)47-48
• 5.3 測(cè)試結(jié)果比較48-50
• 5.4 本章小結(jié)50-51
• 第6章 總結(jié)與展望51-53
• 6.1 論文總結(jié)51
• 6.2 展望51-53
• 致謝53-54
• 參考文獻(xiàn)54-60
• 附錄：WASAT算法源代碼60-78
• 攻讀碩士學(xué)位期間發(fā)表的論文及參與的科研工作78

【相似文獻(xiàn)】

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

1 鄒汪平;;一種基于網(wǎng)絡(luò)安全控制的蜂群算法應(yīng)用研究[J];吉林師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年04期

2 郭毅可;韓銳;;云計(jì)算中的彈性算法:概要和展望[J];上海大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年01期

3 劉江華;戴新喜;白似雪;;基于模式矩陣的P_Matrix算法[J];南昌大學(xué)學(xué)報(bào)(理科版);2007年05期

4 胡俊鵬;;基于雙向選擇的蟻群相遇算法的優(yōu)化[J];湖北民族學(xué)院學(xué)報(bào)(自然科學(xué)版);2013年01期

5 張麗;;關(guān)聯(lián)規(guī)則挖掘算法的研究[J];赤峰學(xué)院學(xué)報(bào)(自然科學(xué)版);2013年02期

6 吳秋峰;尹海東;孟翔燕;;基于和積和最大積的信念傳播算法的收斂性分析[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2011年09期

7 趙吉東;;蟻群算法的改進(jìn)策略研究[J];中國科技信息;2012年12期

8 胡森森;周賢善;;一種改進(jìn)蟻群算法的研究[J];長(zhǎng)江大學(xué)學(xué)報(bào)(自科版);2006年10期

9 王恒娜;趙曉靜;;基于屬性覆蓋的關(guān)聯(lián)規(guī)則挖掘算法[J];安慶師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2007年03期

10 曹建軍;刁興春;李凱齊;邵衍振;;基于進(jìn)化強(qiáng)度的蟻群算法過程性能評(píng)價(jià)[J];解放軍理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年01期

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

1 黃紀(jì)武;毛澤華;李松濤;張錦雄;;SPMD并行查找算法的MPI實(shí)現(xiàn)[A];廣西計(jì)算機(jī)學(xué)會(huì)——2004年學(xué)術(shù)年會(huì)論文集[C];2004年

2 黃紀(jì)武;毛澤華;李松濤;張錦雄;;SPMD并行查找算法的MPI實(shí)現(xiàn)[A];廣西計(jì)算機(jī)學(xué)會(huì)2004年學(xué)術(shù)年會(huì)論文集[C];2004年

3 符麗錦;覃華;鄧海;孫欣;;一種改進(jìn)的Apriori算法的研究[A];廣西計(jì)算機(jī)學(xué)會(huì)2012年學(xué)術(shù)年會(huì)論文集[C];2012年

4 王東鋒;王軍民;陳英武;;模糊定性仿真理論研究與算法實(shí)現(xiàn)[A];'2000系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)交流會(huì)論文集[C];2000年

5 趙唯;;晶粒度評(píng)級(jí)的改進(jìn)算法[A];中國圖象圖形科學(xué)技術(shù)新進(jìn)展——第九屆全國圖象圖形科技大會(huì)論文集[C];1998年

6 劉啟文;;可擴(kuò)展的圖形學(xué)算法演示系統(tǒng)的研究[A];’2004計(jì)算機(jī)應(yīng)用技術(shù)交流會(huì)議論文集[C];2004年

7 佘智;蔣泰;朱延生;;基于Type C協(xié)議的防沖突改進(jìn)算法[A];廣西計(jì)算機(jī)學(xué)會(huì)25周年紀(jì)念會(huì)暨2011年學(xué)術(shù)年會(huì)論文集[C];2011年

8 朱紹文;趙培;朱秋云;;基于pSPADE并行挖掘序列算法的研究[A];2003年中國智能自動(dòng)化會(huì)議論文集（下冊(cè)）[C];2003年

9 楊霞;;新的基于啟發(fā)式蟻群算法的QoS路由算法[A];廣西計(jì)算機(jī)學(xué)會(huì)2009年年會(huì)論文集[C];2009年

10 陳黎飛;姜青山;董槐林;;基于圖形輪廓的快速聚類算法[A];第二十三屆中國數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（研究報(bào)告篇）[C];2006年

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

1 鐘永騰;基于近場(chǎng)MUSIC算法的復(fù)合材料結(jié)構(gòu)健康監(jiān)測(cè)研究[D];南京航空航天大學(xué);2014年

2 單美靜;求解非線性實(shí)代數(shù)系統(tǒng)的混合算法研究[D];華東師范大學(xué);2008年

3 邱劍鋒;人工蜂群算法的改進(jìn)方法與收斂性理論的研究[D];安徽大學(xué);2014年

4 潘磊;若干社區(qū)發(fā)現(xiàn)算法研究[D];南京大學(xué);2014年

5 陳俊波;頻繁閉合項(xiàng)集挖掘算法及應(yīng)用研究[D];浙江大學(xué);2009年

6 陸楠;關(guān)聯(lián)規(guī)則的挖掘及其算法的研究[D];吉林大學(xué);2007年

7 范洪博;快速精確字符串匹配算法研究[D];哈爾濱工程大學(xué);2011年

8 寇曉麗;群智能算法及其應(yīng)用研究[D];西安電子科技大學(xué);2009年

9 劉維;生物序列模式挖掘與識(shí)別算法的研究[D];南京航空航天大學(xué);2010年

10 吳擎;基于模式搜索的類電磁機(jī)制算法研究與應(yīng)用[D];華中科技大學(xué);2013年

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

1 安世勇;命題邏輯中隨機(jī)3-SAT問題算法研究[D];西南交通大學(xué);2015年

2 畢曉慶;油氣探礦權(quán)競(jìng)爭(zhēng)性出讓系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D];中國地質(zhì)大學(xué)(北京);2015年

3 王明明;鐵路大機(jī)與線路固定設(shè)施間距檢測(cè)算法研究[D];西南交通大學(xué);2015年

4 李靜;基于視頻圖像序列的運(yùn)動(dòng)目標(biāo)檢測(cè)與跟蹤算法研究[D];寧夏大學(xué);2015年

5 劉貝玲;基于天地圖的租房平臺(tái)開發(fā)及其關(guān)鍵技術(shù)研究[D];西南交通大學(xué);2015年

6 曹海鋒;IDS中串匹配臭算法并行優(yōu)化研究[D];西安建筑科技大學(xué);2015年

7 周攀;基于蟻群算法的山區(qū)高速鐵路隧道火災(zāi)應(yīng)急疏散最優(yōu)路徑研究[D];西南交通大學(xué);2015年

8 張路奇;基于改進(jìn)蟻群算法的WSN路由協(xié)議的研究[D];中國地質(zhì)大學(xué)(北京);2015年

9 王曉晨;入侵雜草優(yōu)化算法的應(yīng)用與改進(jìn)[D];長(zhǎng)安大學(xué);2015年

10 信琴琴;手勢(shì)控制和識(shí)別算法研究[D];閩南師范大學(xué);2015年

  本文關(guān)鍵詞：命題邏輯中隨機(jī)3-SAT問題算法研究，由筆耕文化傳播整理發(fā)布。

，

本文編號(hào)：472569