【摘要】：可滿足問題在眾多的NP完全問題中被稱為“種子”問題,是因?yàn)檫@個(gè)問題在實(shí)際生活中應(yīng)用非常頻繁,它在計(jì)算機(jī)領(lǐng)域一直備受專家學(xué)者關(guān)注,在人工智能、計(jì)算機(jī)視覺、組合優(yōu)化方面有著諸多的應(yīng)用。鑒于SAT問題的重要性,本文研究了Max-SAT問題。Max-SAT問題的解決方法分為完備算法和不完備算法,完備算法是在長(zhǎng)時(shí)間求解問題后得到問題的最優(yōu)解,而不完備算法是在短時(shí)間內(nèi)得到問題的次優(yōu)解。由于Max-SAT問題是NP難問題,范式難度和規(guī)模不一,采用不完備算法在短時(shí)間內(nèi)解決這個(gè)問題是非常有必要的。本文通過對(duì)無(wú)權(quán)重的Max-SAT問題的研究,提出了一種高效的不完備算法。本算法的目的是找到一組變量賦值,這組變量賦值可以使給定的CNF范式中的可滿足語(yǔ)句數(shù)量最多。本文的主要工作如下:1、本文研究了國(guó)內(nèi)外經(jīng)典的不完備算法:GSAT算法、CCLS算法和基于交叉熵的可滿足算法,分別比較了不同的不完備算法對(duì)范式的預(yù)處理工作。在對(duì)范式的求解過程中,預(yù)處理可以使后續(xù)搜索變量更快。范式中的變量在不同的子句中信息量是不同的。通過對(duì)信息熵的學(xué)習(xí)和研究發(fā)現(xiàn)信息熵可以很好地判別變量在當(dāng)前范式中的重要程度,從而選擇更為重要的變量放入變量池中作為候選變量。因此本文選取信息熵作為第一步預(yù)處理工作,并且信息熵在此之前沒有被應(yīng)用于解決此類問題。2、本算法的目的是挑選對(duì)當(dāng)前范式最優(yōu)的變量,能夠使最多的子句數(shù)目變?yōu)榭蓾M足狀態(tài)。對(duì)預(yù)處理放入候選變量池中的變量,通過使用關(guān)聯(lián)度方法進(jìn)行局部搜索,進(jìn)一步選出更優(yōu)的變量。然后,通過剪枝方法對(duì)變量賦值,使得每次最大可能地減少子句數(shù)量。接著更新范式,執(zhí)行下一次迭代運(yùn)算。3、最后為了驗(yàn)證本文算法的效果,選取基于交叉熵的不完備算法和2016年全球Max-SAT比賽中的算法作為對(duì)比實(shí)驗(yàn)。通過對(duì)實(shí)驗(yàn)結(jié)果的分析,本算法相對(duì)其它算法在搜索可滿足語(yǔ)句數(shù)量上有所提高,同時(shí)還明顯地提高了搜索可滿足語(yǔ)句的速度。
【圖文】：

基于信息熵局部搜索 Max-SAT 算法的基排構(gòu)安排如下：先對(duì)本文研究工作 Max-SAT 和 SAT了國(guó)內(nèi)外相關(guān)工作與相關(guān)理論的研究構(gòu)； Max-SAT 問題涉及到的相關(guān)理論及、熵的理論知識(shí)和基本常用的搜索算續(xù)準(zhǔn)備對(duì)比的 Max-SAT 不完備算法的描述，通過對(duì)不完備算法的研究，T 局部搜索算法，同時(shí)，對(duì)算法從設(shè)

(P) = 1 = (2-1)但是在實(shí)際情況中，應(yīng)用的并不是單一信源，，因而必須從全局出發(fā)，平均在各種情況下事件發(fā)生的不確定性，即得到真實(shí)的信息熵(InformationEntropy)。具體來(lái)講，給定具有 N 種取值可能的信源，這些取值定義為X1, 2 ，相應(yīng)的概率是P1, 2 ，由于各個(gè)信號(hào)彼此相互獨(dú)立，則最終信源的不確定性是求對(duì)單個(gè)信號(hào)的不確定性也就是要求式（2-1）的所有和的平均值，也就是信息熵，定義為 E，我們把這個(gè)具體形式如下：H(X) = = 1 (2-2)一般運(yùn)算中，式中對(duì)數(shù)一般取 2 為底，單位是比特，當(dāng)然不是必須以 2 為底，也可以是其他數(shù)，只是單位不同，都可以換算成以 2 為底的公式。在這里可以舉例最簡(jiǎn)單的二元信源為例，這樣的信源為單符號(hào)信源，取值只能取 0 和 1，即二元信源。假設(shè)存在這樣一個(gè)信源，它產(chǎn)生信號(hào) 0 的概率為 P，那么產(chǎn)生另一個(gè)信號(hào) 1 的概率就是 Q=1-P，由此可以得到如圖 2-1 所示[34]。其中橫坐標(biāo)為概率，縱坐標(biāo)為熵。
【學(xué)位授予單位】：電子科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：TP301.6

【相似文獻(xiàn)】

相關(guān)期刊論文 前5條

1 陳瑞,許進(jìn);MAX-SAT問題的分子信標(biāo)解決方法[J];計(jì)算機(jī)工程與應(yīng)用;2005年20期

2 趙同f;朱文興;;MAX-SAT問題一種改進(jìn)的局部搜索算法[J];計(jì)算機(jī)工程與科學(xué);2008年11期

3 劉飛;;MAX-SAT問題的一種改進(jìn)的禁忌搜索算法[J];福建電腦;2013年02期

4 孫如祥;唐天兵;李炳慧;;并行蟻群算法求解加權(quán)MAX-SAT[J];計(jì)算機(jī)應(yīng)用研究;2012年01期

5 唐天兵;石科;李炳慧;謝祥宏;嚴(yán)毅;;一個(gè)求解加權(quán)MAX-SAT問題的改進(jìn)蟻群算法[J];廣西大學(xué)學(xué)報(bào)(自然科學(xué)版);2010年02期

相關(guān)碩士學(xué)位論文 前2條

1 聶婧;基于信息熵的局部搜索Max-SAT算法[D];電子科技大學(xué);2018年

2 顏遠(yuǎn)輝;賦權(quán)MAX-SAT問題的動(dòng)態(tài)凸化方法[D];福州大學(xué);2011年

本文編號(hào)：2616255