求解QBF问题的启发式调查传播算法

• 作者: 周俊萍 孙吉贵 殷明浩 谷文祥
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 人工智能 QBF问题 QBF问题求解器 因子图 调查传播 冲突学习 满足蕴涵学习
• 年，卷（期）: 2011,（7）
• 所属期刊栏目: 模式识别与人工智能
• 页码范围: 1538-1550
• 分类号: TP181
• 字数: 9859字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2011.03859

摘要

提出了一种启发式调查传播算法,并基于该算法设计了一种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问题求解中的实际价值.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孙吉贵	吉林大学教育部符号计算与知识工程重点实验室	134	2984	21.0	52.0
2	周俊萍	东北师范大学计算机学院	2	14	2.0	2.0
6	谷文祥	东北师范大学计算机学院	71	538	11.0	20.0
7	殷明浩	东北师范大学计算机学院	35	304	10.0	16.0