링크 : 나는 SAT 해결사로 Z3를 사용했습니다
Z3 theorem prover
picosat with pyhton bindingsZ3py : picosat에서 사용 조항에 Z3 공식을 변환
. 더 큰 수식의 경우 성능 문제가있는 것 같아서 피코사스가 더 빠른 대안인지 확인하려고했습니다.
from z3 import *
import pycosat
from pycosat import solve, itersolve
#
#1 2 3 4 5 6 7 8 (variable names in picosat are numbers!)
#
C, G, M, P, R, S, SN, B = Bools('C G M P R S SN B')
C = (And(*(S,Or(Not(S),P),Or(Not(P),S),Or(Not(P),B),Or(Not(C),P),Or(Not(G),P),Or(Not(M),P),Or(Not(R),P),Or(Not(SN),P),Or(Not(B),P),True,Not(False),Or(R,SN,B,G,M,C,True))))
# formula in Z3:
f = simplify(C)
print f
OUTPUT/RESULT Picosat 그러나 다음의 예와 같이 목록/숫자 배열을 사용
And(S,
Or(Not(S), P),
Or(Not(P), S),
Or(Not(P), B),
Or(Not(C), P),
Or(Not(G), P),
Or(Not(M), P),
Or(Not(R), P),
Or(Not(SN), P),
Or(Not(B), P))
("clauses1 : 기존 파이썬 코드 Z3 구문 명제 화학식 생성 ": 6은 변수 P를, -6은"P가 아닙니다 "를 의미합니다.
import pycosat
from pycosat import solve, itersolve
#
# use pico sat
#
nvars = 8
clauses =[
[6],
[-6, 4], ## "Or(Not(S), P)" from OUPUT above
[-4, 6],
[-4, 8],
[-1, 4],
[-2, 4],
[-3, 4],
[-5, 4],
[-7, 4],
[-8, 4]]
#
# efficiently find all models of the formula
#
sols = list(itersolve(clauses, vars=nvars))
print "result:"
print sols
print "\n\n====\n"
르 솔루션을 사용하여 CNF의 수식을 나타내는 Z3 변수 (코드 예제 에서처럼 "f"와 같이)를 CNF의 수식을 나타내는 데 사용되는 앞의 형식으로 변환합니다. 나는 Z3의 python API를 사용하려고 시도했지만, 문서로는 문제를 해결하기에 충분하지 않았습니다.
(단지 개념을 도시 상기 변수 C로 표시되는 화학식을 동적으로 생성 할 것이다. 예를 참고 직접 Z3에 의해 효율적으로 처리하기에 너무 복잡 할 것이다)
피코사스가 합리적으로 효율적인 지 알고 계십니까? 멀티 스레드 된 SAT 해결사가 있습니까? CNF에서 공식을 얻고 변수 이름을 숫자로 대체하는 것은 쉽습니다. Z3의 공식은 이미 CNF에 있습니다. 나를위한 어려운 부분은 수식을 트래버스하고 변환하기 위해 파이썬 API를 사용하는 것입니다. "[[-A, B], [- B, C]]"문자열을 생성하려면 "And (또는 (Not (A), B), Or (Not (B), C))"를 트래버스합니다. 모든 답변에 도움을 주셔서 감사합니다, 또한 다른 사람들에게! (BTW 왜 귀하의 게시물에 파이썬 온라인 예제 많은 링크가 작동하지 않습니다 예 : http://rise4fun.com/Z3Py/E1s – mrsteve
Picosat 매우 효율적입니다 –
몇 가지 멀티 스레드 SAT 해결사가 있습니다 : 예 : manysat (http : /www.cril.univ-artois.fr/~jabbour/manysat.htm) –