摘要：在高密度复杂结构带权无向图中,由于信息传递复杂,传统信息传播算法求解最大权重团问题效率较低。利用最大权重独立集与最大权重团的映射关系提出一种针对高密度带权无向图求解最大权重团问题算法,该算法以最大积信息传播算法为框架,将最大权重团的约束条件与置信传播算法迭代方程相结合,设计信息传播算法势函数。同时,将高密度复杂结构带权无向图映射为因子图,并进行去环操作,利用信息传播迭代式进行特征收敛计算,通过迭代收敛后的最大后验概率计算最大权重团最优解。基于不同密度随机图进行实验对比分析,实验结果表明,该算法求解高密度复杂结构带权无向图最大权重问题时非常有效,求解总权值的准确度与求解速率均高于标准置信传播算法。

摘要：信息传播算法求解可满足问题时有良好的有效性,使得难解区域变窄.然而,信息传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.调查传播(survey propagation,SP)算法是最为有效的信息传播算法,对SP算法的收敛性研究是设计其他信息传播算法的重要基础,并为信息传播算法的广泛应用提供理论依据.为了分析SP算法的收敛性,通过对消息更新方程取双曲正切,将消息取值从[0,1]扩展为(-∞,∞),利用压缩映射原理给出了SP算法收敛的一个充分条件.基于随机3-SAT实例,给出了SP算法收敛的一个概率条件.最后,选取了随机3-SAT实例进行数值实验模拟,验证了该条件的有效性.

摘要：信息传播算法求解可满足性问题时具有良好的有效性,能使难解区域变窄。在信息传播算法的设计中,是将变量的联合概率分布分解为变量子集上的局部函数的乘积形式。称局部函数为因子(factor),每一个因子依赖于一个变量子集,将变量联合分布的这一因子形式表示为图模型——因子图(factor graph)。信息传播算法是通过因子图上的边传递概率消息,这种消息传递有两种方式:变量结点传递给因子结点的消息和因子结点传递给变量结点的消息。从每个结点传出的消息由传入该结点的消息决定,通过某种迭代策略对消息进行更新。当这种消息迭代过程收敛到某一固定点时,利用某种规则(如,最小熵、最大积、最大匹配)对问题进行求解。本文提出一种利用最大匹配规则求解因子图上的信息传播算法的收敛性及算法迭代步数的上界估计方法,根据对算法的收敛性分析,在对问题解的精确性影响不大的前提下,仅需要给出算法合理的迭代步数或者强迫算法终止,使得算法提前结束,有助于求解可满足性问题算法性能的更进一步优化。