摘要
信息传播算法在求解随机kSAT问题时有惊人的效果,难解区域变窄.对于这种现象,至今缺少系统的理论解释.警示传播(warning propagation,简称WP)算法是一种基础的信息传播算法,为有效分析WP算法在随机kCNF公式上的收敛性,给出了随机kCNF公式因子图上圈存在的相变点.在随机kCNF公式产生模型G(n,k,p)中,取k=3,p=d/n2,因子图中圈存在的相变点为p=1/8n2.当d<1/8时,因子图中开始出现圈,且每个连通分支至多有一个圈,因子图中含圈的连通分支的数目以及圈的长度均与n无关.因此,因子图是由森林和一些含有唯一圈的连通分支构成.证明了WP算法在这些实例集上高概率收敛,并且给出了算法的迭代步数为O(logn+s),其中,s为连通分支的大小.
Message propagation algorithms are very effective in finding satisfying assignments for random kSAT instances and hard regions become more narrow. Unfortunately, this phenomenon is still lacks rigorous theoretical proofs. The Warning Propagation （WP） algorithm is the most basic message propagation algorithm. In order to analysis the WP algorithm convergence for random kCNF formulas the study gives the sharp threshold point for the existence of cycles in the factor graph of random kCNF formulas, the threshold for the existence of cycles in model G（n,k,p） of random kCNF formulas is p=1/8n2 for/c=3, p=d/n2. When d becomes asymptotically equal to 1/8, cycles begin to appear, but each component contains at most one cycle, the number of the components containing a single cycle and the length of cycle are a constant independent of n. Thus, the factor graph consists of a forest of trees plus a few components that have a single cycle. Then WHP （with high probability） after at most O（logn＋s） iterations, WP converges on these instances. Here s is the size of the connected component.
出处
《软件学报》
EI
CSCD
北大核心
2013年第1期1-11,共11页
Journal of Software
基金
国家自然科学基金(60863005
61111130186)
贵州大学研究生创新基金(2011033)
关键词
警示传播算法
收敛性分析
相变
可满足性问题
warning propagation algorithm
convergence analysis
phase transition
satisfiability problem
