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

作者： 谢志新 ¹ 王晓峰 ^1,2 于卓 ¹ 曹泽轩 ¹ 吴宇翔 ¹ 莫淳惠 ¹
作者单位：

1. 北方民族大学计算机科学与工程学院

2. 北方民族大学图像图形智能处理国家民委重点实验室
提交时间：2022-05-18 16:08:25

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

警示传播算法收敛性树宽命题公式可满足性问题

期刊： 计算机应用研究
分类： 计算机科学 >> 计算机科学的集成理论
引用： ChinaXiv:202205.00133 (或此版本 ChinaXiv:202205.00133V1)
DOI:10.12074/202205.00133V1
CSTR:32003.36.ChinaXiv.202205.00133.V1
推荐引用方式： 谢志新,王晓峰,于卓,曹泽轩,吴宇翔,莫淳惠.(2022).基于树宽的警示传播算法收敛性分析.计算机应用研究.[ChinaXiv:202205.00133] (点此复制)

版本历史

[V1]

2022-05-18 16:08:25

ChinaXiv:202205.00133V1

下载全文

相关论文推荐

1. Turing’s thinking machine and ’t Hooft’s principle of superposition of states	2024-05-14
2. 恶意代码SCMP分类方法框架与风险行为多标签机制	2024-05-09
3. SteganoDDPM: A high-quality image steganography self-learning method using diffusion model	2024-04-23
4. 引导大语言模型生成计算机可解析内容	2024-04-21
5. 基于大语言模型的中英文整合复杂性建模研究	2024-04-10
6. 大模型与标准文献知识库的融合应用探索	2024-04-10
7. 简体中文LIWC2024(SCLIWC2024)词典的修订与验证	2024-04-09
8. 引导大语言模型生成计算机可解析内容	2024-04-07
9. 基于 Python 中 MeCab 库对日语文章进行文本分析处理实现	2024-04-04
10. 一种基于能量-信息转换的智能测度	2024-03-30


公开评论匿名评论仅发给作者