基于树宽的警示传播算法收敛性分析

警示传播算法作为一种基本的信息传播算法，其收敛时求解可满足性问题十分有效，但因子图结构较为复杂时，算法往往不收敛导致求解失败。为了对这种现象给予理论解释，同时对警示传播算法收敛性进行有效分析，利用树分解方法构造了命题公式对应因子图的树宽度量模型，计算可满足随机实例的树宽。建立树宽与警示传播算法收敛性之间的关系，给出了基于树宽的警示传播算法收敛性判定条件。通过实验分析，结果表明该方法有效，对于分析其他信息传播算法收敛性分析研究具有十分重要的意义。

Convergence analysis of warning propagation algorithm based on tree width

The warning propagation algorithm, as a basic information propagation algorithm, is very effective in solving the satisfiability problem when it converges. However, when the structure of factor graph is more complex, the algorithm often does not converge, resulting in solving failure. In order to give a theoretical explanation for this phenomenon, and to effectively analyze the convergence of warning propagation algorithm, this paper used tree decomposition method to constructed the tree width measurement model of factor graph corresponding to propositional formula, and calculated the tree width that satisfied the random instance. It established the relationship between tree width and convergence of warning propagation algorithm, and gaven the convergence judgment condition of warning propagation algorithm based on tree width. The experimental results show that this method is effective, and it is very important to analyze the convergence of other information transmission algorithms.