调查传播算法和蚁群算法相结合求解可满足性问题

摘要：

布尔可满足性问题(Boolean Satisfiability Problem,SAT)是逻辑学的一个基本问题,也是NP-hard问题.调查传播算法(Survey Propagation,SP)是求解SAT的一种非常高效的算法,但SP在难解区域极易不收敛,或者出现错误赋值.将SP算法与蚁群算法结合,把SP算法得到的消息值应用到蚁群算法中来求解3-SAT问题,使用这些消息值引导蚁群算法求解,并在算法中加入高效的局部搜索.新算法对于SP算法不收敛的一些实例也能很快找到解.

关键词：调查传播算法、难解区域、蚁群算法、局部搜索

所属期刊栏目：39

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金60873078,61165003,61170081;广东省自然科学基金9251064101000010

在线出版日期：2012-07-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：227-231