CAJ | 학술논문

提出了一种启发式调查传播算法,并基于该算法设计了一种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(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문제구해중적실제개치.