| Survey Propagation：一种求解SAT的高效算法 |
| |
| 引用本文： | 李韶华 张健. Survey Propagation：一种求解SAT的高效算法[J]. 计算机科学, 2005, 32(1): 132-137 |
| |
| 作者姓名： | 李韶华 张健 |
| |
| 作者单位： | 中科院软件所,计算机科学实验室,北京,100080 |
| |
| 摘 要： | Survey propagation是一种新生的SAT(CSP)算法。它基于统计物理的spin glass模型，针对具体问题进行纵览(survey)，从而极大地降低求解的复杂度。但sp算法在某些时候不收敛，或引导向错误的解。对此，G．Parisi提出一种复杂回溯(backtrack)算法，而作者在sp中加入简单回溯，也使一部分此类问题得到解决。
|
| 关 键 词： | “Survey Propagation” SAT算法 可满足性问题 求解算法 不完备搜索方法 人工智能 命题逻辑公式 |
Survey Propagation:An Effective Algorithm for Solving SAT |
| |
| LI Shao-Hua,ZHANG Jian Computer Science for Lab.. Survey Propagation:An Effective Algorithm for Solving SAT[J]. Computer Science, 2005, 32(1): 132-137 |
| |
| Authors: | LI Shao-Hua ZHANG Jian Computer Science for Lab. |
| |
| Affiliation: | LI Shao-Hua,ZHANG Jian Computer Science for Lab.,Institute of Software,Chinese Academy of Sciences,Beijing 100080 |
| |
| Abstract: | The Survey propagation is a new SAT(CSP)algorithm. It is a spin glass model based on statistic physics, which makes survey for specific problems, so as to greatly reduce the complexity of solving. But the sp aigorithm sometime is conrergence,or leads to erroneous solutions. For this reason,in this paper,a simple backtraking is induct- ed into SP,thereby partialy solves this kind of SAT problems. |
| |
| Keywords: | Incomplete search SAT Solving algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
