基于函数变换的求解SAT问题的新算法

摘要：

提出了一种基于函数变换的求解SAT问题的新算法,这个新算法利用SAT问题自身的特点将判定问题转化为连续函数的求极值问题.随机选取一组初始值,利用最速下降法求解变换后的连续函数在每个初始值邻域内所能达到的局部极值,如果这个局部极值为0,则该SAT问题就是可满足的.实验结果表明:与现有的求解SAT问题的算法相比,基于函数变换的求解算法在求解速度、成功率和求解问题的规模等方面都有明显的提高.

关键词：SAT问题、局部搜索算法、函数变换、最速下降法

所属期刊栏目：2

分类号：TP391.5(计算技术、计算机技术)

在线出版日期：2012-09-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：33-36,39