计算机应用研究

作者：牛进,王晓峰,林青文,

单位：北方民族大学计算机科学与工程学院,银川750021；

关键词：可满足性问题,命题公式,结构熵,警示传播算法,收敛性,

基金：国家自然科学基金资助项目(61462001,61762019,61862051,61962002)；北方民族大学重大专项资助项目(ZDZX201901)；宁夏自然科学基金资助项目(NZ17111,2019AAC03120,2019AAC03119)；北方民族大学校级科研一般项目(2019XYZJK05)；；

收敛性是评价信息传播算法性能的重要指标，信息传播算法求解可满足性问题时，命题公式的结构特征影响算法的收敛性，具有复杂结构的命题公式，信息传播算法不总收敛。为了系统地对此现象给予理论解释，借助于结构熵的方法和技术，提出命题公式的结构熵模型及其度量方法，计算随机可满足性实例的结构熵。警示传播算法（WP）作为信息传播算法的基本模型，分析WP算法的收敛性对于研究其他信息传播算法的收敛性具有重要意义，分析了WP算法收敛性与结构熵之间的关系，给出WP算法收敛的判定条件。通过实验分析，该方法有效可行。

来源：2021年第3期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2021年第3期