首页 | 本学科首页   官方微博 | 高级检索  
     

SAT问题中局部搜索法的改进
引用本文:杨晋吉,苏开乐.SAT问题中局部搜索法的改进[J].计算机研究与发展,2005,42(1):60-65.
作者姓名:杨晋吉  苏开乐
作者单位:1. 中山大学信息科学与技术学院计算机科学系,广州,510275;华南师范大学计算机科学系,广州,5106313
2. 中山大学信息科学与技术学院计算机科学系,广州,510275;河南科技大学电子信息工程学院,洛阳,471003
基金项目:国家自然科学基金项目(60473004) 教育部留学回国人员科研启动基金项目
摘    要:局部搜索方法在求解SAT问题的高效率使其成为一研究热点.提出用初始概率的方法对局部搜索算法中变量的初始随机指派进行适当的约束.使在局部搜索的开始阶段,可满足的子句数大大增加,减少了翻转的次数,加快了求解的速度.用该方法对目前的一些重要的SAT问题的局部搜索算法(如WSAT,TSAT,NSAT,SDF等)进行改进,通过对不同规模的随机3-SAT问题的实例和一些不同规模的结构性SAT问题的实例,以及利用相变现象构造的难解SAT实例测试表明,改进后的这些局部搜索算法的求解效率有了很大的提高.该方法对其他局部搜索法的改进具有参考价值。

关 键 词:SAT问题  局部搜索  概率

Improvement of Local Research in SAT Problem
Yang Jinji,Su Kaile.Improvement of Local Research in SAT Problem[J].Journal of Computer Research and Development,2005,42(1):60-65.
Authors:Yang Jinji  Su Kaile
Abstract:Recently, local search methods for solving the SAT problem have attracted considerable attention because they are the best known approaches to several hard classes of satisfiability. In this paper, an efficient initial probability is presented, which can constrain the random initial assignment of variables in the local search method. Also discussed is how to use the initial probability to improve the current local search algorithms such as WSAT, NSAT, TSAT, SDF, etc. . The strategies are straightforward and intuitive, and are helpful for increasing the number of satisfied clauses at its beginning of local search, thus decreasing the number of flipping for finding a solution and making the local search process converge fast. For this method to be compared with the other current local algorithms, many general random 3-SAT problem instances, structured SAT problem instances in SATLIB and phase transition' s SAT problem instances are tested. The actual experimental results indicate that the improved algorithms are more efficient than the current local search SAT solvers such as WSAT, and so on. Moreover, this method can also be applied to other related methods to improve, their efficiency.
Keywords:SAT problem  local search  probability
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号