基于膨脹圖的隨機(jī)算法求解SAT問(wèn)題.pdf

1、膨脹圖是有很好連通性的稀疏圖。它的每一個(gè)不太大的結(jié)點(diǎn)集都有一個(gè)相對(duì)更大的鄰接結(jié)點(diǎn)集，因此，要想使圖不連通，需要切斷許多邊。由于膨脹圖的這一特性，使得它在理論與實(shí)踐中發(fā)揮著極其重要的作用，橫跨數(shù)學(xué)、通信和計(jì)算機(jī)等多個(gè)領(lǐng)域，如算法設(shè)計(jì)、密碼學(xué)、糾錯(cuò)碼、偽隨機(jī)信號(hào)發(fā)生器、排序網(wǎng)絡(luò)及健壯的計(jì)算機(jī)網(wǎng)絡(luò)等方面。在理論計(jì)算機(jī)科學(xué)中，由于膨脹圖在某些方面與隨機(jī)圖類(lèi)似，尤其是能夠降低隨機(jī)算法對(duì)隨機(jī)位的依賴(lài)程度，因此正越來(lái)越引起科學(xué)家們的關(guān)注，被用于證明計(jì)

2、算復(fù)雜性理論的許多結(jié)論。 我們知道，命題公式的可滿足性問(wèn)題是理論計(jì)算機(jī)科學(xué)和人工智能中的著名問(wèn)題，判斷命題公式可滿足性的一個(gè)直接辦法是窮舉法。這種辦法從理論上講是可行的，但計(jì)算時(shí)間動(dòng)輒達(dá)到天文數(shù)字。而其它算法，如DPLL算法、局部隨機(jī)搜索算法等也各有其優(yōu)缺點(diǎn)。因此，高效實(shí)用的SAT算法設(shè)計(jì)與分析一直是計(jì)算機(jī)科學(xué)界的研究熱點(diǎn)。 本文對(duì)膨脹圖的理論進(jìn)行了較為全面的分析，并以膨脹圖為基礎(chǔ)，提出了一種新的SAT算法。首先，從組合

3、學(xué)角度介紹了膨脹圖的基本概念和性質(zhì)；其次，從代數(shù)學(xué)角度對(duì)膨脹圖族的構(gòu)造進(jìn)行研究，介紹了正則圖的三種積運(yùn)算：矩陣積、直積、替換積，并利用三種積各自的特點(diǎn)進(jìn)行膨脹圖族的構(gòu)造；再次，從概率論角度對(duì)膨脹圖的隨機(jī)步進(jìn)行深入研究，詳細(xì)介紹了膨脹混合引理及隨機(jī)步概率估計(jì)，進(jìn)而將膨脹圖應(yīng)用于隨機(jī)算法的設(shè)計(jì)；最后，對(duì)可滿足性問(wèn)題、隨機(jī)算法、SAT算法的分類(lèi)進(jìn)行介紹，并將膨脹圖與已有的SAT算法相結(jié)合，利用膨脹圖來(lái)誘導(dǎo)SAT算法搜索的隨機(jī)步，最終提出了基于