CMP设计分享 http://blog.sciencenet.cn/u/accsys 没有逆向思维就没有科技原创。 不自信是科技创新的大敌。

博文

你有SAT问题?我来帮你解答

已有 4585 次阅读 2017-6-2 08:37 |个人分类:SAT问题|系统分类:科研笔记| 人工智能, CESAT

你有SAT问题?我来帮你解答

姜咏江

我们不谈3-SAT问题是否是关系到开放的P/NP问题,只谈3-SAT问题的求满足解的算法快慢。如果你的问题可以转化为布尔电路可满足性问题,那么很幸运,这个问题有了在一定变量数之后,较指数时间快的多项式时间算法了。

本人宣布过在理论上解决了SAT问题的多项式时间算法。如今我已经将理论转化成了计算机软件程序CESAT。最坏的3-SAT问题,CESAT程序可以在O(n4)时间复杂度内得到满足解。根据研究,在变量数充分大之后,指数时间复杂度的求解程序无法在短时间内获得结果,而多项式时间复杂度的程序CESAT可以做到。

下面是CESAT程序运行时间测试。

例子1.  200个变量和500个子句的3-SAT,程序运行时间和结果如图1所示。

1  CESAT的执行结果与运行时间

1中开始的时间是111035,找出全部唯一解变量的时间是11:15:42,中间程序运行57秒。另外,程序结束的时间是111545,总共运行的时间是510秒。

这是一般情况下的求3-SAT满足解的例子。为了说明CESAT的快速,再执行一个对子句消去法最坏情况的例子。

例子2.  2为所有变量都有2个可选解的3-CNF。这是将其前11列连续编排10次,得到了有110个变量的3-CNFCESAT在求解的过程中要判断每个变量的可选解数量,由于没有唯一解变量,因而会消耗较多的时间。

2   变量全为2个可选解

CASAT对此题进行的测试,用了33分钟17秒。如图3所示,唯一解部分没有任何变量值,全部变量值都出现在有2个可选解的情况。



3  CASAT得出结果运行时间

上面两个例子反映出了CESAT程序针对3-CNF=1求解的实际情况。毫无疑问,在变量充分一样多,最坏的情况下也会体现出CESAT的快速本质。

为了清楚,我们简单说明一下指数时间和多项式时间的问题,以及CESAT的优势。

最简单的指数函数为y=2n,而4次多项式为y=a0+a1n1 +a2 n2 +a3 n3 +a4 n4。依据算法时间复杂度理论,计算机操作时间计算,只要比较多项式的最高项即可。在计算机中可以取2的幂的数,于是选有n=2m。这样就有22m次幂与24m相等的点,即有2m=4m这个时间点。容易得到m超过4,也就是n超过16就可以满足指数时间超过4次多项式时间的要求。全面考虑多项式,总可以找到一个确定的n0,使n继续变大的时候,y=2n的上升速度高于y=a0+a1n1 +a2 n2 +a3 n3 +a4 n4

一般情况下,不要以为算法的多项式时间就是一、二次多项式那样快。3-SAT问题一般情况,最低要超过有65536个变量的情况下,才可以说多项式y=a0+a1n1 +a2 n2 +a3 n3 +a4 n4算法比y=2n这个指数时间算法要快。但子句消去法CESAT的优势是依据限位数理论,快速找出了那些有唯一解的变量值,进而可以大大地减少了需要重复操作的变量的数量,并依据剩余变量可选解集做为记忆的形式,通过“联想”和“忘记”迅速获得满足解。这种特征无疑是人工智能的理论和实现基础。

我没有编写和使用过DPLL程序。用过DPLL程序的朋友,一定会有客观的感受。

相信我,就可以联系我。

2017-06-02




https://blog.sciencenet.cn/blog-340399-1058546.html

上一篇:Algorithm ZJXQF for SAT Problem
下一篇:计算机时代的数学家应该有新思维了
收藏 IP: 118.144.20.*| 热度|

0

该博文允许注册用户评论 请点击登录 评论 (4 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-12-7 05:19

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部