帶隨機(jī)步的可滿足性算法.pdf

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

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

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