%0 Journal Article
%T 规则实例集上警示传播算法的收敛性
%A 王晓峰？
%A 李强？
%A 丁红胜？
%J 计算机科学
%D 2015
%R 10.11896/j.issn.1002-137X.2015.01.062
%X 信息传播算法求解随机3-sat问题时非常有效,能使难解区域变窄。然而,对于因子图带有环的实例,信息传播算法并不总有效,常表现为不收敛。对于这种现象,至今缺少系统的理论解释。警示传播(warningpropagation,wp)算法是一种基础的信息传播算法,对wp算法的收敛性研究是其它信息传播算法收敛性研究的重要基础。将一个3-sat问题转换为具有规则结构的(3,4)-sat问题,(3,4)-sat问题是np-完全的。基于(3,4)-sat问题的规则结构性质,分析wp算法的收敛性。选取了3组不同规模的实例进行实验模拟,结果表明:在这种规则结构的可满足性实例集上,wp算法的收敛性有较大提高。
%K 警示传播算法
%K 收敛性
%K 可满足性问题
%K 规则结构
%U http://www.jsjkx.com/jsjkx/ch/reader/view_abstract.aspx?file_no=20150162&flag=1