规则实例集上警示传播算法的收敛性

信息传播算法求解随机3-sat问题时非常有效,能使难解区域变窄。然而,对于因子图带有环的实例,信息传播算法并不总有效,常表现为不收敛。对于这种现象,至今缺少系统的理论解释。警示传播(warningpropagation,wp)算法是一种基础的信息传播算法,对wp算法的收敛性研究是其它信息传播算法收敛性研究的重要基础。将一个3-sat问题转换为具有规则结构的(3,4)-sat问题,(3,4)-sat问题是np-完全的。基于(3,4)-sat问题的规则结构性质,分析wp算法的收敛性。选取了3组不同规模的实例进行实验模拟,结果表明:在这种规则结构的可满足性实例集上,wp算法的收敛性有较大提高。