淺談3-sat問題的判定

1、淺談3-SAT問題,陳昕昀,SAT問題的定義,,k-SAT,3-SAT,完備性算法非完備性算法一些拓展,完備性算法,根本思想:回溯法優(yōu)化: (1)優(yōu)先確定短的子句中包含的變量的值 (2)優(yōu)先確定在較多子句中出現(xiàn)的變量的值,問題模型的轉(zhuǎn)化,問題模型的轉(zhuǎn)化,將X中所有變量的一個賦值方案記為 a={a1,a2,…,an}令則原問題轉(zhuǎn)化為判斷上述函數(shù)最小值 能否達(dá)到0,非完備性算法,爬山法模

2、擬退火遺傳算法 ……,粒子群優(yōu)化算法,J. Kennedy,R. C. Eberhart(1995)第i個粒子的狀態(tài)用三元組(ai,vi,pi)表示 ai:當(dāng)前解 vi:粒子運動速度 pi:該粒子達(dá)到過的最優(yōu)解,應(yīng)用于3-SAT問題,記ai=(xi1, xi2,…, xin) vi=(vi1,vi2,…, vin)(ai,vi,pi)的更新方式如下:

3、 當(dāng)sig(vij(t+1))≤r3時,xij(t+1)=0,反之為1 其中t為迭代次數(shù),sig(x)=1/(1+e-x) ω∈(0,1),為慣性因子;c1,c2為事先確定的正常數(shù) pg表示整個粒子群所達(dá)到過的最優(yōu)解 r1,r2,r3為相互獨立的(0,1)之間的隨機(jī)數(shù),單純用這種方法求解容易使f(pg)停留在某個很小的正整數(shù)而無法得到0這個解有可能在最優(yōu)解的附近記當(dāng)前所得f(p

4、g)=c;若最優(yōu)解存在的話,至多需要改變 3c個變量的值將其余變量的值固定,對這幾個變量使用局部隨機(jī)搜索若仍無法達(dá)到最優(yōu)解,則認(rèn)為當(dāng)前解為局部極小值,更新其余解,應(yīng)用于3-SAT問題,偽代碼,maxTimes=200, vmax=2;size=100,c1=c2=2.0,w=0.8,i=1,currentTimes=0;initialize population;while ivmax)vij=vmax;

5、 get r3; if sig(vij)<=r3 then xij=0 else xij=1; end for,偽代碼,if currentTimes>=maxTimes then while 1 do c=f(pg); c2=local_search(pg); if c2=0 then return pg; if c2<=c then

6、 update pg else i=i+1,currentTimes=0,break; end while end thenend while return (pg,f(pg));,一些拓展,轉(zhuǎn)化為獨立集問題對Xi’中每個元素建立一個節(jié)點對應(yīng)于相應(yīng)變量 的取值,并兩兩之間相互連邊假如Xi’與Xj’中同時存在xk和￢ xk,將對應(yīng)的兩個 點連邊3-SAT問題有解當(dāng)且僅當(dāng)該圖中存在點數(shù)為m

7、 的獨立集,一些拓展,轉(zhuǎn)化為獨立集問題舉個例子:,一些拓展,一個8/7-近似算法假設(shè)在一個3-SAT問題中每個語句恰好包含3個 子句,如果我們只要求滿足大部分語句的話,存在 一個確定性算法能夠滿足7/8的語句首先,考慮在一隨機(jī)指派下滿足語句個數(shù)的期望 值,記為E(X),每個語句記為Xi則P(Xi=1)=7/8,P(Xi=0)=1/8,E(Xi)=7/8(1≤i≤m)故 E(X)=7m/8因此,基于隨機(jī)

8、指派的算法的期望近似比≤m/(7m/8)=8/7,一些拓展,一個8/7-近似算法首先考慮變量x1由于E(X)=E(X|x1=1)P(x1=1)+E(X|x1=0)P(x1=0) =0.5E(X|x1=1) +0.5E(X|x1=0)故必存在對于x1的某個賦值a1(a1∈{0,1})使得 E(X|x1=a1)≥7m/8同理,可依次找到a2, a3 …,an∈{0,1}使得 E

9、(X| x1=a1,…, xn=an)≥7m/8,則該方案即為所求該確定性算法的近似比≤m/(7m/8)=8/7,時間復(fù) 雜度為O(nm),結(jié) 語,References,Carla P. Gomes, Henry Kautz, Ashish Sabharwal, Bart Selman,“Satisfiability solvers”He Yichao,Wang Yanqi,Kou Yingzhan, “A New