| 信息传播算法收敛的后门集 |
| |
| 引用本文： | 王晓峰,许道云,秦永彬. 信息传播算法收敛的后门集[J]. 西南交通大学学报, 2012, 25(1): 32-38,62. DOI: 10.3969/j.issn.0258-2724.2012.021.01.006 |
| |
| 作者姓名： | 王晓峰 许道云 秦永彬 |
| |
| 作者单位： | 贵州大学计算机科学系 |
| |
| 基金项目： | 国家自然科学基金资助项目(60863005);贵州大学研究生创新基金的资助(校研理工2011033) |
| |
| 摘 要： | 为了探讨WP(警示传播)算法的收敛性,给出了WP算法收敛的后门集.通过对此后门集中的变元赋值,可将布尔公式简化成其因子图为树型结构的子公式,WP算法在子公式上收敛.最后,设计了一个求解该后门集的随机算法,并分析了该算法的可行性.结果表明,所提出的求解该后门集的随机算法是有效的.
|
| 关 键 词： | 信息传递算法 警示传播算法 原理分析 后门集 算法收敛性 |
| 收稿时间： | 2011-03-11 |
Backdoors of Message Propagation Algorithm Convergence |
| |
| WANG Xiaofeng,XU Daoyun,QIN Yongbin. Backdoors of Message Propagation Algorithm Convergence[J]. Journal of Southwest Jiaotong University, 2012, 25(1): 32-38,62. DOI: 10.3969/j.issn.0258-2724.2012.021.01.006 |
| |
| Authors: | WANG Xiaofeng XU Daoyun QIN Yongbin |
| |
| Affiliation: | (Department of Computer Science,Guizhou University,Guiyang 550025,China) |
| |
| Abstract: | 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. |
| |
| Keywords: | message passing algorithm warning propagation algorithm principle analysis backdoors convergence of algorithm |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《西南交通大学学报》浏览原始摘要信息 |
|
点击此处可从《西南交通大学学报》下载全文 |
|
