摘要
提出了一种基于函数变换的求解SAT问题的新算法,这个新算法利用SAT问题自身的特点将判定问题转化为连续函数的求极值问题。随机选取一组初始值,利用最速下降法求解变换后的连续函数在每个初始值邻域内所能达到的局部极值,如果这个局部极值为0,则该SAT问题就是可满足的。实验结果表明:与现有的求解SAT问题的算法相比,基于函数变换的求解算法在求解速度、成功率和求解问题的规模等方面都有明显的提高。
A new algorithm based on Function transformation is proposed for salving SAT problems in this paper. The algorithm firstly makes use of the characteristics of a SAT problem, changes it tO a extreme-value problem of continuous function, and then chooses a set of initial value randomly further uses steepest descent method to solve the local minimum of the transformed continuous function in each neighborhood of the initial value. If minimum value is 0, then the corresponding SAT problem is satiable. The experimental results show that the algorithm based on Function Transformation performs remarkably better than the existing algorithms to solve the SAT problem in the aspects of speed, the success rate and the problem scales.
出处
《智能计算机与应用》
2012年第3期33-36,39,共5页
Intelligent Computer and Applications
关键词
SAT问题
局部搜索算法
函数变换
最速下降法
SAT Problem
Local Search Algorithm
Function Transformation
Steepest Descent Method
