Survey Propagation:一种求解SAT的高效算法

摘要：

Survey propagation是一种新生的SAT(CSP)算法.它基于统计物理的spin glass模型,针对具体问题进行纵览(survey),从而极大地降低求解的复杂度.但sp算法在某些时候不收敛,或引导向错误的解.对此,G.Parisi提出一种复杂回溯(backtrack)算法,而作者在sp中加入简单回溯,也使一部分此类问题得到解决.

关键词：不完备搜索方法、可满足性问题、求解算法

所属期刊栏目：32

分类号：TP2;TN2

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

页数：共6页

页码：132-137