计算机应用研究

作者：谢志新,王晓峰,于卓,曹泽轩,吴宇翔,莫淳惠,

单位：北方民族大学a.计算机科学与工程学院;b.图像图形智能处理国家民委重点实验室,银川750021；

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

基金：国家自然科学基金资助项目(62062001,61762019,61862051,61962002)；宁夏自然科学基金资助项目(2020AAC03214,2020AAC03219,2019AAC03120,2019AAC03119)；北方民族大学重大专项资助项目(ZDZX201901)；北方民族大学研究生创新项目(YCX22197)；；

警示传播算法作为一种基本的信息传播算法，其收敛时求解可满足性问题十分有效，但因子图结构较为复杂时，算法往往不收敛导致求解失败。为了对这种现象给予理论解释，同时对警示传播算法收敛性进行有效分析，利用树分解方法构造了命题公式对应因子图的树宽度量模型，计算可满足随机实例的树宽。建立树宽与警示传播算法收敛性之间的关系，给出了基于树宽的警示传播算法收敛性判定条件。通过实验分析，结果表明该方法有效，对于分析其他信息传播算法收敛性分析研究具有十分重要的意义。

来源：2022年第10期

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

查看计算机应用研究杂志2022年第10期