| RB模型实例集上置信传播算法的收敛性 |
| |
| 引用本文： | 王晓峰,许道云. RB模型实例集上置信传播算法的收敛性[J]. 软件学报, 2016, 27(11): 2712-2724 |
| |
| 作者姓名： | 王晓峰 许道云 |
| |
| 作者单位： | 北方民族大学 计算机科学系, 宁夏 银川 750021;贵州大学 计算机科学系, 贵州 贵阳 550025,贵州大学 计算机科学系, 贵州 贵阳 550025 |
| |
| 基金项目： | 国家自然科学基金（61462001，61262006） |
| |
| 摘 要： | 置信传播算法求解RB（k，n，α，rc，p）模型实例时非常有效，几乎能够有效求解接近可满足性相变点的难解实例.然而，因子图带有回路的实例，置信传播算法不总有效，常表现为不收敛.对于这种现象，至今缺少系统的理论解释.置信传播算法是最为基础的信息传播算法，对置信传播算法的收敛性分析是其他信息传播算法收敛性分析的重要基础.在RB（k，n，α，rc，p）模型中，取k=2，α>（1/k），rc>0均为常数，且满足ke-（α/（rc））≥1.证明了如果p∈（0，n-2α），则置信传播算法在RB（k，n，α，rc，p）模型产生的随机实例集上高概率收敛.最后，在RB（k，n，α，rc，p）模型上选取了几组不同的数据进行数值模拟，实验结果表明该结论有效.当问题规模n增大时，在RB（k，n，α，rc，p）模型的可满足区域，实验收敛区间趋于一个固定范围，而理论收敛区间逐渐变窄.原因在于，RB（k，n，α，rc，p）模型是一个具有增长定义域的随机CSP实例产生模型，不协调赋值的数目与参数p及问题规模n有关.
|
| 关 键 词： | 置信传播算法 收敛性 约束可满足性问题 RB 模型 |
| 收稿时间： | 2014-03-09 |
| 修稿时间： | 2015-03-10 |
Convergence of the Belief Propagation Algorithm for RB Model Instances |
| |
| WANG Xiao-Feng and XU Dao-Yun. Convergence of the Belief Propagation Algorithm for RB Model Instances[J]. Journal of Software, 2016, 27(11): 2712-2724 |
| |
| Authors: | WANG Xiao-Feng and XU Dao-Yun |
| |
| Affiliation: | Department of Computer Science, Beifang University of Nationalities, Yinchuan 750021, China;Department of Computer Science, Guizhou University, Guiyang 550025, China and Department of Computer Science, Guizhou University, Guiyang 550025, China |
| |
| Abstract: | |
| |
| Keywords: | belief propagation algorithm convergence constraint satisfaction problem RB model |
|
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
