首页 | 官方网站   微博 | 高级检索  
     

一个求解结构SAT问题的高效局部搜索算法
引用本文:梁东敏,吴晔,马绍汉.一个求解结构SAT问题的高效局部搜索算法[J].计算机学报,1998,21(Z1):92-97.
作者姓名:梁东敏  吴晔  马绍汉
作者单位:山东大学计算机科学系,济南,250100
基金项目:国家自然科学基金,国家高技术研究发展计划(863计划),,,,
摘    要:逻辑表达式可满足性(SAT)问题是第一个被证明的NP完全问题.它也是解决人工智能和计算理论中许多实际问题的基础.人们发现,对于某些类型的SAT问题,局部搜索算法要比一些传统的算法(例如Davis-Putnam过程)更为有效.在本文中,我们主要讨论如何用局部搜索算法求解结构SAT问题.我们对一个典型的局部搜索算法GSAT+walk做了改进与扩展.首先,我们除去了GSAT+walk中GSAT部分的"平移";其次,我们给每一个子句赋权,并在GSAT+walk的搜索过程中动态地调整子句的权.文中给出的实验结果表明改进后的新算法对于求解结构SAT问题非常有效.

关 键 词:可满足性问题  局部搜索
修稿时间:1996年5月17日

AN EFFICIENT LOCAL SEARCH ALGORITHM FOR STRUCTURED SAT PROBLEMS
LIANG Dong-Min,WU Ye,MA Shao-Han.AN EFFICIENT LOCAL SEARCH ALGORITHM FOR STRUCTURED SAT PROBLEMS[J].Chinese Journal of Computers,1998,21(Z1):92-97.
Authors:LIANG Dong-Min  WU Ye  MA Shao-Han
Abstract:
Keywords:
本文献已被 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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

京公网安备 11010802026262号