求解可满足问题的调查传播算法以及步长的影响规律

• 作者: 李光辉 李晓维 邵明
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 可满足问题 因子图 调查传播算法 局部搜索算法 相变
• 年，卷（期）: 2005,（5）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 849-855
• 页数: 7页
• 分类号: TP306
• 字数: 5000字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2005.05.013

摘要

该文研究了求解可满足问题的调查传播算法.该算法利用合取范式因子图进行调查消息的迭代,并根据每一次迭代的收敛情况对部分布尔变量赋值以对问题进行简化,最后把简化的问题利用局部搜索算法来求解.文中所谓步长是指在每一次迭代收敛之后根据赋值倾向进行赋值的变量个数.该文根据模拟实验观察到步长对调查传播算法的影响规律,即随着步长的递增,算法的时间耗费以及算法的有效性都有近似单调递减的趋势.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李晓维	中国科学院计算技术研究所信息网络室	127	1467	20.0	32.0
5	邵明	中国科学院计算技术研究所信息网络室	36	161	8.0	11.0
9	李光辉	中国科学院计算技术研究所信息网络室	17	172	9.0	13.0