收稿日期:20181120;修回日期:20190115 基金项目:国家自然科学基金资助项目 (61462001,61762019,61762002,11761002,
61561002);北方民族大学重点科研项目(2017KJ24,2017KJ25);2018宁夏回族自治区重点研发计划项目(2018BEE03019);宁夏高等学校一流学科
建设(电 子 科 学 与 技 术 学 科 )资 助 项 目 (NXYLXK2017A07);北 方 民 族 大 学 创 新 项 目 (YCX19060);北 方 民 族 大 学 校 级 科 研 一 般 项 目
(2019XYZJK05);宁夏自然科学基金资助项目(NZ17111,2019AAC03120,2019AAC03119)
作者简介:崔立(1994),男,陕西宝鸡人,硕士研究生,主要研究方向为算法分析与设计;王晓峰(1980),男,甘肃会宁人,副教授,博士,主要
研究方向为机器学习、算法分析与设计(xfwang@nun.edu.cn);牛进(1993),男,陕西安康人,硕士研究生,主要研究方向为人工智能.
WP可解公式上警示传播算法收敛的有效条件
崔 立,王晓峰,牛 进
(北方民族大学 计算机科学与工程学院,银川 750021)
摘 要:通过对警示传播(warningpropagation,WP)算法的数学原理分析,高概率确定的部分变元与公式的骨干
集和后门集有密切关系。针对 WP算法收敛性的研究,基于骨干集和后门集定义 WP可解公式,利用在 G(n,3,
m)模型和植入指派模型下证明 WP算法的收敛性,给出算法收敛的充要条件。最后,通过在植入指派的公式产
生模型上进行数值实验验证,结果表明:如果一个可满足性公式 WP可解公式,当且仅当 WP算法高概率收敛。
关键词:警示传播算法;骨干集;后门集;WP可解公式;实例产生模型
中图分类号:TP301.6 文献标志码:A 文章编号:10013695(2020)05024140605
doi:10.19734/j.issn.10013695.2018.11.0791
Effectiveconditionsforwarningpropagationalgorithm
convergenceonWPsolvableformula
CuiLi,WangXiaofeng,NiuJin
(SchoolofComputerScience&Engineering,NorthMinzuUniversity,Yinchuan750021,China)
Abstract:ThroughtheanalysisofthemathematicalprincipleofWPalgorithm,itcouldbefoundthatthepartialvariablesde
terminedbyhighprobabilityarecloselyrelatedtothebackbonesetandbackdoorsetoftheformula.Forthestudyofthecon
vergenceofWPsolvableformulaandWPalgorithm,thispaperdefinedWPsolvableformulabasedonbackbonesetandback
doorset,andprovedtheconvergenceoftheWPalgorithmbyusingtheG(n,3,m)modelandtheplanteddistributionmodel,
itgavethenecessaryandsufficientconditionsfortheconvergenceofthealgorithm.Finally,itcarriedoutthenumericalexper
imentsonthemodeloftheplanteddistributionformula.TheresultsshowthatifasatisfiabilityformulaWPsolvableformula
,if
andonlyiftheWPalgorithmhasahighprobabilityofconvergence.
Keywords:warningpropagationalgorithm;backboneset;backdoorset;WPsolvableformula;instancegenerationmode
0 引言
约束可满足性问题(constraintsatifiabilityproblem,CSP)是
人工智能中一个重要的研究领域
[1~3]
,SAT(satisfiability)问题
是典型的 CSP
[4~6]
。SAT问题的 NP完全性表明,不存在多项
式时间算法求解该问题。然而现实世界中很多复杂问题通过
编码都可以转换为
SAT问题,如机器人路径规划、智能系统知
识推理、大型复杂系统控制等。尽管 SAT问题是 NP难的,随
着研究的不断深入以及硬件的发展,SAT问题求解器越来越智
能,使得难解区域变窄,甚至能够在多项式时间内求解变相点
附近的难解实例。梳理这几年的研究成果,
SAT问题研究主要
集中在两个方面:
a)通过构造实例产生模型,分析该问题的相变现象。最
具有代表性的是随机 3SAT实例产生模型 G(n,3,m),该模型
中子句与变元的比值
α
=m/n是一个重要的参数,它不仅仅影
响实例的可满足性,而且影响实例的判定难度
[7]
。随机统计
现象表明,对于随机 3SAT实例产生模型 G(n,3,m),存在可
满足的相变点
α
d
,当
α
<
α
d
时,实例高概率可满足;当
α
>
α
d
时,实例高概率不可满足
[8]
。把满足与不可满足之间出现的
这种临界现象称为相变现象,
α
d
称为相变点,在相变点附近区
域的实例求解难度较大。尽管人们不知道
α
d
的确切值,但研
究表明,
α
d
至少为 3.52
[9]
,至多为 4.4898
[10]
。在该模型中,
通过控制参数
α
来构造实例,大量的实验研究表明,当
α
的值
大约在
4.27附近时,产生的实例求解难度最大。Xu等人
[11,12]
分别在 B模型和 D模型的基础上提出了具有精确相变点的
RB和 RD模型,解决了经典 CSP实例产生模型的平凡无解性
问题,被广泛用于构造 CSP和 SAT问题的难解实例。
b)设计更加有效的求解 SAT问题的判定算法
[13]
。大多
数 SAT问题求解算法利用了隐藏在实例内部的某种特殊结
构,较大程度地提高了算法的搜索能力,而骨干集和后门集是
SAT实例中最为重要的结构,在算法求解过程中起关键性作
用。Monasson和 Silliams等人在研究可满足性问题的相变现
象和复杂度时,首次提出了骨干集和后门集的概念
[14]
。骨干
集和后门集都与问题的难度相关,骨干集越大,问题的难度越
大;同样,后门集越大,问题的难度越大
[15]
。事实上,对于一些
结构化的实例,骨干集和后门集有一定的联系
[16~20]
。现实世
界中许多具有结构化的 SAT问题都有较小的骨干集和后门
集,一些著名的搜索算法利用了这种结构特征,求解这些实际
问题往往比求解随机 3SAT更为有效
[14]
。
在 SAT问题判定算法的研究中,人们发现实例的隐藏结
构对算法的性能有影响,最为重要的隐藏结构主要有骨干集和
后门集。骨干集是文字的集合,指对于一个可满足命题公式的
每一个真值指派使得骨干集中的文字均为真;后门集是变元的
集合,指对后门集中的变元赋值后将相应的命题公式化简为易
第 37卷第 5期
2020年 5月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol.37No.5
May2020