-
题名求解QBF问题的启发式调查传播算法
被引量：11
- 1
-
-
作者
殷明浩
周俊萍
孙吉贵
谷文祥
-
机构
东北师范大学计算机学院
吉林大学教育部符号计算与知识工程重点实验室
吉林大学计算机科学与技术学院
-
出处
《软件学报》
EI
CSCD
北大核心
2011年第7期1538-1550,共13页
-
基金
国家自然科学基金(60773097
60803102)
-
文摘
提出了一种启发式调查传播算法,并基于该算法设计了一种QBF(quantified Boolean formulae)求解器——HSPQBF(heuristic survey propagation algorithm for solving QBF)系统.它将Survey Propagation信息传递方法应用到QBF求解问题中.利用Survey Propagation作为启发式引导DPLL(Davis,Putnam,Logemann and Loveland)算法,选择合适的变量进行分支,从而可以减小搜索空间,并减少算法回退的次数.在分支处理过程中,HSPQBF系统结合了单元传播、冲突学习和满足蕴涵学习等一些优秀的QBF求解技术,从而能够提高QBF问题的求解效率.实验结果表明,HSPQBF无论在随机问题上还是在QBF标准测试问题上都有很好的表现,验证了调查传播技术在QBF问题求解中的实际价值.
-
关键词
人工智能
QBF问题
QBF问题求解器
因子图
调查传播
冲突学习
满足蕴涵学习
-
Keywords
artificial intelligence
quantified Boolean formulae problem
QBF（quantified Boolean formulae）solver
factor graph
survey propagation
conflict driven learning
satisfiability directed implicationand learning
-
分类号
TP181
[自动化与计算机技术—控制理论与控制工程]
-
