|||
你有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中开始的时间是11:10:35,找出全部唯一解变量的时间是11:15:42,中间程序运行5分7秒。另外,程序结束的时间是11:15:45,总共运行的时间是5分10秒。
这是一般情况下的求3-SAT满足解的例子。为了说明CESAT的快速,再执行一个对子句消去法最坏情况的例子。
例子2. 图2为所有变量都有2个可选解的3-CNF。这是将其前11列连续编排10次,得到了有110个变量的3-CNF。CESAT在求解的过程中要判断每个变量的可选解数量,由于没有唯一解变量,因而会消耗较多的时间。
图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。这样就有2的2m次幂与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
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-12-7 05:19
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社