博文
速度对比：一个可以快速求解的3SAT例题
|||
速度对比：一个可以快速求解的3SAT例题
姜咏江
表1是手工求解的结果，最快用了8分钟。
表1
0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | x15 | x16 | x17 | x18 | x19 | x20 |
下面是用子句消去法程序执行后得到的同一道3SAT题的满足解，仅仅用了2.1秒。用此程序求100个变量的3SAT满足解，也只用了不到9秒的时间。
用子句消去法不仅能够快速求出3-SAT的满足解，而且能够确定3-SAT是否无解。
参考：http://blog.sciencenet.cn/blog-340399-981402.html
2016-6-4
https://wap.sciencenet.cn/blog-340399-982414.html
上一篇：一个可以快速求解的3SAT例题 ——答案
下一篇：为k-SAT问题彻底解决欢呼，感谢杜立智的精彩评论
