RB模型实例集上置信传播算法的收敛性

• 作者: 王晓峰 许道云
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 置信传播算法 收敛性 约束可满足性问题 RB模型
• 年，卷（期）: 2016,（11）
• 所属期刊栏目: 模式识别与人工智能
• 页码范围: 2712-2724
• 页数: 13页
• 分类号: TP181
• 字数: 11134字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.004877

摘要

置信传播算法求解RB(k,n,α,rc,p)型实例时非常有效,几乎能够有效求解接近可满足性相变点的难解实例.然而,因子图带有回路的实例,置信传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.置信传播算法是最为基础的信息传播算法,对置信传播算法的收敛性分析是其他信息传播算法收敛性分析的重要基础RB(k,n,α,rc,p))模型中,取k=-2,α＞1/k,rc＞0均为常数,且满足ke-ac/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有关.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许道云	贵州大学计算机科学系	125	460	12.0	16.0
2	王晓峰	北方民族大学计算机科学系	26	122	6.0	9.0