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