帶隨機步的可滿足性算法.pdf

1、滿足性問題是研究如何判定一個任意給定的邏輯表達(dá)式是否存在可滿足真值指派，它是人工智能、計算理論和理論計算機科學(xué)中的最矚目問題之一，它是第一個被證明的NP完全問題，在計算復(fù)雜性理論中起著很重要的作用。求解SAT問題一般分為完全算法和非完全算法兩類。如果一個SAT實例有可滿足解，完全算法能夠找到可滿足解，如果這個SAT實例無解，完全算法能給出所有解都是不可滿足的證明，但需要花指數(shù)級時間；對于一個可滿足的SAT實例，非完全算法一般都能以很高的

2、概率找到其可滿足解，雖然對一些滿足解很少的SAT實例不能找到其滿足解，但是非完全算法能在多項式時間內(nèi)結(jié)束算法，所以非完全算法在實際應(yīng)用中得到了廣泛的應(yīng)用。 隨機算法是求解SAT問題的一種重要的非完全算法，就是在算法中引入隨機化，算法中根據(jù)隨機數(shù)選擇下一步的操作。隨機算法的一般框架是隨機地選取一個給定SAT實例的解，驗證其是否滿足，如果滿足，算法結(jié)束；否則，就根據(jù)隨機源所產(chǎn)生的隨機數(shù)選擇下一個解，直到找到一個滿足解或者到t個解后算

3、法結(jié)束。在隨機算法中由隨機源產(chǎn)生隨機數(shù)，但真正的隨機源很難得到，一般用偽隨機數(shù)發(fā)生器來代替，這也是隨機算法的一個致命弱點。改進(jìn)的辦法有兩種：一種是改進(jìn)偽隨機數(shù)發(fā)生器；另一種是在不改變算法的性能的情況下，盡量減少偽隨機數(shù)的產(chǎn)生，從而減少算法對隨機位的依賴。 本文研究的是后一種方法，在隨機算法中引入膨脹圖，利用膨脹圖的性質(zhì)去誘導(dǎo)算法中的隨機步，減少算法中偽隨機數(shù)的產(chǎn)生，進(jìn)而減少算法對隨機數(shù)的依賴和偽隨機數(shù)對算法的影響。一般的隨機算法