求解恰当可满足性问题的随机局部搜索算法

可满足性问题(SAT)是一种NP完全问题,被广泛运用于人工智能和机器学习等研究。恰当可满足性问题(XSAT)是SAT中一类重要的子问题。目前的大部分关于XSAT的研究主要为理论层面,对高效的求解算法特别是具有高效验证性的随机局部搜索算法研究很少。针对以上问题,分析了基础编码和等价编码两种转化方式的公式的部分性质,提出一种直接求解XSAT的随机局部搜索算法WalkXSAT。首先使用随机局部搜索框架进行基础搜索与条件判定;其次加入变元所属文字的恰当不可满足计分值,优先处理不易恰当满足的变元;然后使用防重复选择翻转变元的启发式策略减小搜索空间;最后,采用多种来源以及多种格式的实例进行对比实验。在直接求解XSAT时,相较于ProbSAT,WalkXSAT的变元翻转次数与求解时间显著减少;在求解基础编码转化后的实例中,当实例变元规模大于100时,ProbSAT已失效,而WalkXSAT依然能够在短时间内求解。实验结果表明,所提WalkXSAT精确性高、稳定性强、收敛快。

基于动态奖惩的分支策略的SAT完备算法

针对学习子句数量有限或相似度高导致历史信息有限、搜索树不平衡的问题,提出了基于动态奖惩的分支策略。首先,对每次单子句传播的变元进行惩罚,依据变元是否产生冲突和产生冲突的间隔,确立不同的惩罚函数;其次,在学习阶段,利用学习子句确定对构造冲突有益的变元,非线性增加它们的活跃度;最后,选择活跃度最大的变元作为新分支变元。在glucose3.0算法基础上,完成了改进的动态奖惩算法——AP7。实验结果表明,相比glucose3.0算法,AP7算法的剪枝率提高了14.2%~29.3%,少数算例剪枝率的提高可达51%,且改进后的AP7算法相比glucose3.0算法,运行时间缩短了7%以上。所提分支策略可以有效降低搜索树规模,使搜索树更加平衡,减少计算时间。

一类可分离SAT问题的O(1.890~n)精确算法

布尔可满足性问题(SAT)是指对于给定的布尔公式,是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题,一般认为不存在多项式时间算法,除非P=NP.学者们大都研究了子句长度不超过k的SAT问题(k-SAT),从全局搜索到局部搜索,给出了大量的相对有效算法,包括随机算法和确定算法.目前,最好算法的时间复杂度不超过O((2-2/k)~n),当k=3时,最好算法时间复杂度为O(1.308~n).而对于更一般的与子句长度k无关的SAT问题,很少有文献涉及.引入了一类可分离SAT问题,即3-正则可分离可满足性问题(3-RSSAT),证明了3-RSSAT是NP完全问题,给出了一般SAT问题3-正则可分离性的O(1.890~n)判定算法.然后,利用矩阵相乘算法的研究成果,给出了3-RSSAT问题的O(1.890~n)精确算法,该算法与子句长度无关.

随机正则恰当(d,k)-SAT问题的可满足相变分析

为深入理解随机正则恰当(d,k)-SAT问题难解的内在本质,理清相变与难解之间的变化规律,进一步设计高效的求解算法,引入随机正则恰当可满足性实例产生模型,采用一阶矩和二阶矩方法分析了该问题的相变情况,给出了正则恰当(d,k)-SAT问题的可满足相变点d^(*).当相变控制参数d^(*)时,正则恰当(d,k)-SAT问题实例高概率可满足;当d>d^(*)时,正则恰当(d,k)-SAT问题实例高概率不可满足.最后,选取子句长度k分别为3和4进行实验,结果表明:在d^(*)的取值分别为2.3798和3.0668附近发生了相变现象,进一步证明了理论结果与实验结果的一致性.

随机均衡正则恰当(2s,k)-SAT问题的可满足相变

为深入理解均衡正则恰当(2s,k)-SAT问题的判定难度和可满足性解的分布情况,引入随机实例产生模型,利用一阶矩和二阶矩方法分析可满足性相变现象,给出随机均衡正则恰当(2s,k)-SAT问题可满足的相变点s∗.当s<s∗时,随机均衡正则恰当(2s,k)-SAT实例高概率可满足;当s>s∗时,随机均衡正则恰当(2s,k)-SAT实例高概率不可满足.最后,选取了k=4和k=6的两组数据集进行实验验证,结果表明理论结果与实验结果符合.