首页 | 本学科首页   官方微博 | 高级检索  
     

基于警示传播与DPLL算法的启发式极性决策算法
引用本文:秦永彬,许道云,王晓峰.基于警示传播与DPLL算法的启发式极性决策算法[J].计算机科学,2010,37(12):178-181.
作者姓名:秦永彬  许道云  王晓峰
作者单位:贵州大学计算机科学与信息学院,贵阳,550025
基金项目:本文受国家自然科学基金(60863005,61011130038),贵州省省长基金(200404),贵州大学自然科学青年基金(2009021)资助。
摘    要:警示传播(WP)算法是信息传播算法的重要基础,WP算法的本质是因子图上警示信息的迭代过程,在算法收敛时得到一组稳定的警示信息,并利用局部腔域得到公式变元的部分赋值。分析了警示传播算法的基本原理,给出了算法的改进。RB实例集上的实验证明,改进后的算法比原算法具有迭代次数和运行时间,提高了收敛速度。然而,在RB模型产生的大部分实例集上,警示传播算法不收敛,因而不能有效求解公式。警示传播算法与DPLL算法的组合使用使回溯计算次数大大降低,从而有效地弥补了WP算法的不足。通过在RI3实例集上的测试实验表明,该方法是有效的。

关 键 词:信息传递,警示传播算法,收敛性,DPLL算法

Heuristic Polarity Decision Making Algorithm Based on Warning Propagation and DPLL Algorithm
QIN Yong-bin,XU Dao-yun,WANG Xiao-feng.Heuristic Polarity Decision Making Algorithm Based on Warning Propagation and DPLL Algorithm[J].Computer Science,2010,37(12):178-181.
Authors:QIN Yong-bin  XU Dao-yun  WANG Xiao-feng
Affiliation:(College of Computer Science and Information,Guizhou University,Guiyang 550025,China)
Abstract:The warning propagation(WP) algorithm is an important foundation of message propagation algorithm, the essence of the WP algorithm is the iteration process of warning message on the factor gragh. When the algorithm is convergent, it can get a set of stable warning message and get some partial assignment of formula variables by local cavity domain. The analysis of basic principle of the WP algorithm was presented, and the improvement of the algorithm was given.The experiment on the RB sets shows that the improved algorithm has fewer iteration times, less execute time and faster convergence speed than the original WP algorithm. However, in the most of the RB sets, the WP algorithm is not convergent,and then it can not solve the formula effectively. The combination of the WP and DPLL algorithm can reduce the times of the backing calculation,and then up the shortage of the WP algorithm. The result of the experiment on the RB sets shows that the method is effective.
Keywords:Message passing  Warning propagation(WP) algorithm  Convergence  DPLL algorithm
本文献已被 万方数据 等数据库收录!
点击此处可从《计算机科学》浏览原始摘要信息
点击此处可从《计算机科学》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号