信息传播算法收敛的后门集  

Backdoors of Message Propagation Algorithm Convergence

作　　者：王晓峰[1] 许道云[1] 秦永彬[1] 

机构地区：[1]贵州大学计算机科学系,贵州贵阳550025

出　　处：《西南交通大学学报》2012年第1期32-38,62,共8页Journal of Southwest Jiaotong University

基　　金：国家自然科学基金资助项目(60863005);贵州大学研究生创新基金的资助(校研理工2011033)

摘　　要：为了探讨WP(警示传播)算法的收敛性,给出了WP算法收敛的后门集.通过对此后门集中的变元赋值,可将布尔公式简化成其因子图为树型结构的子公式,WP算法在子公式上收敛.最后,设计了一个求解该后门集的随机算法,并分析了该算法的可行性.结果表明,所提出的求解该后门集的随机算法是有效的.In order to investigate the convergence of the WP（warning propagation） algorithm,backdoors of the WP algorithm were given.By assigning values to variables in the backdoors,the Boolean formula can be simplified to sub-formula having factor graph with tree structures,and the convergence of the WP algorithm can be guaranteed in the sub-formula.Finally,a randomized algorithm for solving the backdoors was designed and its feasibility was analyzed.The result show that the randomized algorithm is feasible.

关 键 词：信息传递算法 警示传播算法 原理分析 后门集 算法收敛性 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]