随机可满足实例集上警示传播算法的收敛性

信息传播算法在求解随机ksat问题时有惊人的效果,难解区域变窄.对于这种现象,至今缺少系统的理论解释.警示传播(warningpropagation,简称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为连通分支的大小.