基于膨脹圖的隨機算法求解SAT問題.pdf

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

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

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