论文部分内容阅读
逻辑表达式可满足性（SAT）问题是第一个被证明的NP完全问题．它也是解决人工智能和计算理论中许多实际问题的基础．人们发现，对于某些类型的SAT问题，局部搜索算法要比一些传统的算法（例如Davis－Putnam过程）更为有效．在本文中，我们主要讨论如何用局部搜索算法求解结构SAT问题．我们对一个典型的局部搜索算法GSAT＋walk做了改进与扩展．首先，我们除去了GSAT＋walk中GSAT部分的“平移”；其次，我们给每一个子句赋权，并在GSAT＋walk的搜索过程中动态地调整子句的权．文中给出的实验结果表明