实例结构限制下信息传播算法的收敛性研究

项目名称： 实例结构限制下信息传播算法的收敛性研究

项目编号： No.61462001

项目类型： 地区科学基金项目

立项/批准年度： 2015

项目学科： 自动化技术、计算机技术

项目作者： 王晓峰

作者单位： 北方民族大学

项目金额： 45万元

中文摘要： 信息传播算法求解可满足性问题时具有良好的有效性，能使难解区域变窄。然而，对于因子图含有回路的可满足性实例，信息传播算法不总有效，常表现为不收敛。对于这种现象，至今缺少系统的理论解释。本项目主要研究实例结构限制下信息传播算法的收敛性。RB(k,n,a,r,p)实例和(3,4)-SAT实例具有一定的结构限制(如，子句长度均等是一种最简单和常见的限制），其对应的因子图是一个规则结构的二部图。基于该实例的规则结构性质，研究信息传播算法在这种结构限制下的收敛性，并给出算法收敛的条件。研究内容包括：(3,4)-SAT实例产生模型、相变分析及测试算法；RB(k,n,a,r,p)实例和(3,4)-SAT实例的因子图结构性质及相应的控制参数；RB(k,n,a,r,p)实例和(3,4)-SAT实例上信息传播算法的收敛性及算法迭代步数的上界估计；警示传播算法存在唯一固定点的条件；信息传播算法的原理及性能改进。

中文关键词： 信息传播算法；可满足性问题；收敛性；因子图；规则实例

英文摘要： Message passing algorithms are very effective in finding satisfying assignments for SAT instances, and hard region become narrower. However, the message passing algorithms do not always converge for factor graph with cycles. Unfortunately, rigorous theory proof of this phenomenon is still lacking. In this project,we study the performance and convergence of message passing algorithms for regular structures instances.The RB(k,n,a,r,p) instances and (3,4)-SAT instances have regular structures,the factor graph of those instances are regular structure bipartite graphs.So we study the convergence of the message passing algorithms on regular structures RB(k,n,a,r,p) and (3,4)-SAT instances, and give convergence conditions of message passing algorithms .It includes (1)Presenting random models producing (3,4)-CNF formulas and analyzing critical properties of random (3,4)-SAT based on properties of regular bigaphes from regular formulas. (2)Investigating the factor graph structures and controls parameters of RB(k,n,a,r,p) and (3,4)-SAT instances. (3)Investigating the convergence of the message passing algorithms for solving (3,4)-SAT instances and RB(k,n,a,r,p) instances,and estimating bounds of iterations number of message passing algorithms. (4)According to Markov chain theory, investigating probability convergence conditions and unique fixed point of the warning propagation algorithm. (5)Improving the performance of message passing algorithms and analyzing the message passing algorithms principle.

英文关键词： message passing algorithms;satisfiability problem;convergence;factor graph;regular instances