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

编号 zgly0000384775

文献类型 期刊论文

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

作者 邵明  李光辉  李晓维 

作者单位 中国科学院计算技术研究所信息网络室  中国科学院计算技术研究所信息网络室 

母体文献 计算机学报 

年卷期 2005,28(5)

页码 849-855

年份 2005 

分类号 TP306 

关键词 可满足问题  因子图  调查传播算法  局部搜索算法  相变 

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