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

打开文本图片集

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

网站仅支持在线阅读（不支持PDF下载），如需保存文章，可以选择【打印】保存。