10.3321/j.issn:0254-4164.2005.05.013
求解可满足问题的调查传播算法以及步长的影响规律
该文研究了求解可满足问题的调查传播算法.该算法利用合取范式因子图进行调查消息的迭代,并根据每一次迭代的收敛情况对部分布尔变量赋值以对问题进行简化,最后把简化的问题利用局部搜索算法来求解.文中所谓步长是指在每一次迭代收敛之后根据赋值倾向进行赋值的变量个数.该文根据模拟实验观察到步长对调查传播算法的影响规律,即随着步长的递增,算法的时间耗费以及算法的有效性都有近似单调递减的趋势.
可满足问题、因子图、调查传播算法、局部搜索算法、相变
28
TP306(计算技术、计算机技术)
国家自然科学基金90207002,60242001;北京市科研项目H020120120130;中国科学院计算技术研究所资助项目20026180-6
2005-06-16(万方平台首次上网日期,不代表论文的发表时间)
共7页
849-855