2011年11月11日星期五

2-SAT

总算release了,释放一下,找个简单的问题自娱自乐一把。
n个变量组成m个子句的句子,其中每个子句中恰有两个变量用或连接,每个变量可以替换成他自身的取反,子句之间用且连接。
给一个这样的句子s,求一组真值分配。

算法:
如果存在一个不成立的子句,就反转其中一个变量。
反复为之,直至超过循环的最大次数。

(听到一个声音说:这叫什么狗屁算法,这不就是在瞎蒙么!)

实现:
import random, re

sentence = lambda n, m: " and ".join(["(%sx%d or %sx%d)" % (
                random.choice(["not ", ""]), random.randint(1, n),
                random.choice(["not ", ""]), random.randint(1, n)) for i in xrange(m)])

def detect_self_contradict(sub):
        (i, j) = re.match(".*?(\d+).*?(\d+)", sub).groups()
        ret = i == j and sub.count("not") == 1
        if ret: print i
        return ret

def solve(s, a):
        for _i in xrange(10000):
                print _i, a
                exec(";".join(["x%d=%s" % (i+1, a[i]) for i in xrange(len(a))]))
                if eval(s): return a
                for sub in s.split("and"):
                        if not eval(sub):
                                i = int(random.choice(re.match(".*?(\d+).*?(\d+)", sub).groups())) - 1
                                a[i] = not a[i]
                                break
        return "failed to solve %s" % s

a=[True]*20
s=sentence(len(a), 24)
if any([detect_self_contradict(sub) for sub in s.split("and")]):
        print "no way! %s" % s
        exit()
print s
print solve(s,a)

一次试验:
python 2sat.py 
(x19 or x6) and (not x1 or x20) and (x5 or not x20) and (x14 or not x20) and (x4 or x2) and (not x19 or x2) and (not x15 or not x6) and (x8 or not x15) and (x9 or not x17) and (not x11 or x4) and (not x16 or not x4) and (not x17 or not x11) and (x20 or x20) and (not x12 or not x16) and (x13 or not x10) and (x3 or not x17) and (x17 or x14) and (not x10 or not x6) and (not x13 or x19) and (x3 or x1) and (not x5 or x8) and (x15 or not x3) and (x1 or x1) and (x3 or x4)
0 [True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True]
1 [True, True, True, True, True, False, True, True, True, True, True, True, True, True, True, True, True, True, True, True]
2 [True, True, True, False, True, False, True, True, True, True, True, True, True, True, True, True, True, True, True, True]
3 [True, True, True, False, True, False, True, True, True, True, False, True, True, True, True, True, True, True, True, True]
4 [True, True, True, False, True, False, True, True, True, True, False, True, True, True, True, False, True, True, True, True]
[True, True, True, False, True, False, True, True, True, True, False, True, True, True, True, False, True, True, True, True]

我试验了很多次,发现凡是有解的时候,都不需要迭代很多次。

再分析:
如果存在一个满足句子s的真值分配A,那么令当前分配X[k]与A相同的变量个数为f(A, X[k])。
每次循环,至少有一半的概率f(A,X[k+1])=f(A, X[k]) + 1

为了证明这一点,假设一个当前未满足的子句X或Y,A以概率p取T,T,以1-p的概率取T,F或F,T。当前取值X[k]显然为F,F,那么f(A,X[k+1])=f(A, X[k]) + 1的概率依全概率公式得
p*1+(1-p)*0.5=0.5+0.5p>=0.5
证毕

f(A,X[k+1])=n时,我们就求得了一个真值分配。


这个试验告诉我们一个道理:如果你相信存在一个真理,并且在实践中发现每次尝试的试错概率不超过一半,并且每次尝试成功都可以向真理靠近一个常数距离,那么,你就大胆地去不断尝试吧!(听到一个声音说:这叫什么狗屁道理。。。)


1 条评论:

123qws 说...

这是local search, 迭代次数小于2n^2的概率为1/2