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

【Abstract】 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.更多还原