摘要
布尔可满足性问题(Boolean Satisfiability Problem,SAT)是逻辑学的一个基本问题,也是NP-hard问题。调查传播算法(Survey Propagation,SP)是求解SAT的一种非常高效的算法,但SP在难解区域极易不收敛,或者出现错误赋值。将SP算法与蚁群算法结合,把SP算法得到的消息值应用到蚁群算法中来求解3-SAT问题,使用这些消息值引导蚁群算法求解,并在算法中加入高效的局部搜索。新算法对于SP算法不收敛的一些实例也能很快找到解。
Satisfiability problem is a basic problem in logic,and also is NP-hard.Survey propagation（SP） is a very effective algorithm for this problem.However,SP tends not to converge in hard region,or gives wrong assignments to the variables.An algorithm combined with SP and ant colony optimization（ACO） was proposed.The messages calculated in SP were used in ACO as guidance to help ACO find a solution.And local search was conducted in the new algorithm.The new algorithm can quickly find solutions for some instances that SP doesn＇t work.
出处
《计算机科学》
CSCD
北大核心
2012年第4期227-231,共5页
Computer Science
基金
国家自然科学基金(60873078
61165003
61170081)
广东省自然科学基金(9251064101000010)资助
关键词
调查传播算法
难解区域
蚁群算法
局部搜索
Survey propagation
Hard region
Ant colony optimization
Local search
