Page 144 - 《软件学报》2021年第5期

1368 Journal of Software 软件学报 Vol.32, No.5, May 2021

可满足 难度

4.27 m/n 4.27 m/n
(a) 可满足相变 (b) 求解难度
Fig.3 Properties change of random 3-SAT instance with parameter m/n
图 3 随机 3-SAT 实例的特征随参数 m/n 的变化情况
1 2.5
n=60
0.9 n=120
0.8 2
0.7
0.6 n=60 1.5
n=120
收敛率 0.5 时间(s)
0.4 1
0.3
0.2 0.5
0.1
0 0
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5
约束参数α=m/n 约束参数α=m/n
(a) 收敛性 (b) 运行时间(s)

Fig.4 Properties change of convergence and time of BP with parameter m/n
图 4 BP 算法的收敛性和运行时间随参数 m/n 的变化情况

定理 3 中,要求计算矩阵的谱半径.图 5 为随机 3-SAT 实例的约束参数α与对应矩阵的谱半径之间的关系.
参数ρ随着约束参数α的变化情况,纵坐标表示谱半径ρ,横坐标表示约束参数α.当α<2.0 时,实例的谱半径小于
0.7,由定理 3 可知,BP 算法能够到达收敛状态.当约束参数α>2.0 时,谱半径ρ几乎不小于 1,定理 3 失效,无法判定
BP 算法的收敛性.直观上,α越小,因子图的结构就越简单,对应的方阵 M 越稀疏,谱半径ρ越接近 0;相反,α越大,
因子图的结构就越复杂,谱半径ρ也越大,可能导致定理 3 中的判定条件失效.
本文与文献[53]类似,都可用于约束可满足性问题的收敛性判定.其他文献主要用于其他问题,与本文没有
可比性.所以,我们把本文结论与文献[53]中的结论做了比较,见表 1.由于可满足性问题实例的求解难度与问题
的规模无关,实验中取 n=120.结合图 3(a)和图 4,选取约束参数α的值分别为 1.0,2.0,3.0,4.0,5.0 进行比较,每个数
据点随机生成 100 个实例.表 1 中的数据表示能够判定 BP 算法收敛的实例数占总实例数的比例,可以看出:当
α<2.0 时,本文结论优于文献[53]中的结论;当α=3.0 和α=4.0 时,本文结论比文献[53]结论略差.然而,通过实验发
现,验证文献[53]中判定条件远比本文条件复杂,在实际应用中可操作性不高.