求解QBF 问题的启发式调查传播算法
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金(60773097, 60803102)


Heuristic Survey Propagation Algorithm for Solving QBF Problem
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    This paper presents a heuristic survey propagation algorithm for solving Quantified Boolean Formulae (QBF) problem. A QBF solver based on the algorithm is designed, namely HSPQBF (heuristic survey propagation algorithm for solving QBF). This solver is a QBF reasoning engine that incorporates Survey Propagation method for problem solving. Using the information obtained from the survey propagation procedure, HSPQBF can select a branch accurately. Furthermore, when handling the branches, HSPQBF uses efficient technology to solve QBF problems, such as unit propagation, conflict driven learning, and satisfiability directed at implication and learning. The experimental results also show that HSPQBF can solve both random and QBF benchmark problems efficiently, which validates the effect of using survey propagation in a QBF solving process.

    参考文献
    相似文献
    引证文献
引用本文

殷明浩,周俊萍,孙吉贵,谷文祥.求解QBF 问题的启发式调查传播算法.软件学报,2011,22(7):1538-1550

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2008-07-18
  • 最后修改日期:2010-03-29
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号