命題公式的可滿足性（SAT）問題作為一類重要的NP完全問題,與人工智能中許多復(fù)雜性問題密切相關(guān)。然而,隨著人工智能領(lǐng)域的快速發(fā)展,為了滿足新的需求,需要重新審視和設(shè)計(jì)SAT問題原有的求解算法,因此,SAT問題在當(dāng)下面臨新的機(jī)遇和挑戰(zhàn)。上世紀(jì)八十年代,物理學(xué)家提出了一種基于消息傳遞的信息傳播算法,將該算法用于SAT問題的求解得到的效果十分顯著,因此一直被學(xué)者廣泛應(yīng)用和研究。然而,由于該算法在相變區(qū)域有時(shí)不收斂,算法表現(xiàn)為失效。而對(duì)于這種現(xiàn)象,目前仍缺少系統(tǒng)的理論解釋。因此本文基于WP-可解公式展開對(duì)信息傳播算法的收斂性研究,力圖從理論上給予對(duì)于算法收斂性現(xiàn)象的解釋。主要研究內(nèi)容如下:（1）分析信息傳播算法的原理,找出信息傳播算法下的骨干集和后門集之間的關(guān)系,并給出WP-可解公式的定義;（2）基于WP-可解公式的特點(diǎn),借助于植入指派實(shí)例產(chǎn)生模型,研究信息傳播算法在WP-可解公式上的收斂性,給出信息傳播算法收斂的一個(gè)有效條件:信息傳播算法在公式F上高概率收斂,當(dāng)且僅當(dāng)公式F是WP-可解公式。本文給出了信息傳播算法收斂的條件,為信息傳播算法的基礎(chǔ)研究以及在人工智能領(lǐng)域的應(yīng)用提供了理論支持。 

【文章來源】：北方民族大學(xué)寧夏回族自治區(qū)

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

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

【部分圖文】：

復(fù)雜性類圖

北方民族大學(xué)2020屆碩士學(xué)位論文第二章理論知識(shí)9圖2-1復(fù)雜性類圖2.1.2因子圖從系譜學(xué)上講，因子圖是對(duì)Wiberg等人的“Tanner圖”的直接概括[58,59]。Tanner[60]引入了二部圖來描述Gallager的低密度校驗(yàn)碼(LDPC)的推廣碼族，并基于此情況描述了合積算法。在Tanner的原始公式中，所有變量都是碼字符號(hào)，由此可見，Wiberg等人介紹了隱藏狀態(tài)變量，并提出了編碼之外的應(yīng)用，因子圖將這些圖論模型進(jìn)一步應(yīng)用于函數(shù)中。因子圖可以用函數(shù)因子分解的二分圖表示，所以若給定一個(gè)函數(shù)12(,,...,)nbMMM，則可以對(duì)其進(jìn)行因式分解，121(,,...,)()mnjjjbMMMcS(2-1)其中，12{,,...,}jnSMMM，變量頂點(diǎn)12{,,...,}nIMMM構(gòu)成相應(yīng)的因子圖G(I,C，E)，因子頂點(diǎn)12{,,...,}mCccc和邊為E。因子圖可以與消息傳遞算法相結(jié)合，有效地計(jì)算函數(shù)12(,,...,)nbMMM的某些特征，如邊緣分布。假設(shè)12345b(m,m,m,m,m)是具有五個(gè)變量的函數(shù)，b可以表示五個(gè)變量的乘積12345121233435(,,,,)()()(,,)(,)(,)ABCDEbmmmmmcmcmcmmmcmmcmm(2-2)將符號(hào)記為：1212334{,,,,}{},{},{,,},{,}ABCDJABCDE，MmMmMmmmMmm和35{,}EMmm，則圖2-2表示公式2-2對(duì)應(yīng)的因子圖。圖2-2121233435()()(,,)(,)(,)ABCDEcmcmcmmmcmmcmm乘積的因子圖

北方民族大學(xué)2020屆碩士學(xué)位論文第二章理論知識(shí)10設(shè)一個(gè)CNF公式為12{,,...,}mFCCC，12,,..nxxx代表有n個(gè)變元，i代表變元ix。因子圖是G{CX,E}能夠描述公式F。其中，用X{1,2,...,n}來表示變量結(jié)點(diǎn)集，功能結(jié)點(diǎn)集為12{,,...,}mCCCC。圖G中的邊分為兩類：實(shí)連接和虛連接。實(shí)連接：(,)iCjE子句iC含正文字jx；虛連接：(,)iCjE子句iC含負(fù)文字jx。由于WP算法使用于因子圖上，因此在求解SAT問題時(shí)，需要將一個(gè)SAT問題轉(zhuǎn)化為因子圖，如下圖2-3所示。在因子圖中包含兩種節(jié)點(diǎn)，變量節(jié)點(diǎn)和功能節(jié)點(diǎn)。在圖中用圓圈表示的是變量節(jié)點(diǎn)，或稱為變量，每個(gè)變量都與圖中的頂點(diǎn)相關(guān)；在圖中用方框表示的是功能節(jié)點(diǎn)，或稱為子句，每個(gè)子句都與圖中的另外頂點(diǎn)相關(guān)聯(lián)。當(dāng)子句A中包含變量ix時(shí)，功能節(jié)點(diǎn)A通過邊的方式與變量節(jié)點(diǎn)相連，當(dāng)子句中出現(xiàn)的變量為ix時(shí)，a和i之間用實(shí)線（1aiJ），當(dāng)子句中出現(xiàn)的變量為ix時(shí)，a和i之間用虛線（1aiJ）。變量節(jié)點(diǎn)構(gòu)成的集合X（XN），功能節(jié)點(diǎn)的集合A（AM）。如果因子圖中有6個(gè)變量節(jié)點(diǎn)i1,...,6和6個(gè)功能節(jié)點(diǎn)a,b,c,d,e,f，則這個(gè)公式可以寫為：13124353452466F(xx)(xxx)(xx)(xxx)(xxx)(x)圖2-3因子圖2.2信息傳播算法若SAT問題中因子圖是樹形結(jié)構(gòu)(樹形問題)，可滿足性問題可以用多種方法求解。本節(jié)將描述兩種消息傳播算法。第一種稱為警示傳播，它確定樹形問題是否為SAT問題；如果是SAT問題，WP算法會(huì)找到一個(gè)可滿足性賦值；第二種算法稱為信念傳播(BP)，它計(jì)算可滿足賦值的數(shù)量，以及給定變量為真時(shí)賦值的比例。這些算法對(duì)樹型問題是精確的，但它們可以作為一般問題的啟發(fā)。

【參考文獻(xiàn)】：
期刊論文
[1]警示傳播算法收斂的充分條件[J]. 王曉峰,許道云.  軟件學(xué)報(bào). 2016(12)
[2]隨機(jī)可滿足實(shí)例集上警示傳播算法的收斂性[J]. 王曉峰,許道云,韋立.  軟件學(xué)報(bào). 2013(01)
[3]求解公式關(guān)鍵文字集的信息傳播算法[J]. 王曉峰,許道云,秦永彬.  山東大學(xué)學(xué)報(bào)(工學(xué)版). 2011(03)



本文編號(hào)：3333397