基于树宽的警示传播算法收敛性分析

分类： 计算机科学 >> 计算机科学的集成理论 提交时间： 2022-05-18 合作期刊: 《计算机应用研究》

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

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

 点击量 394  下载量 196  评论