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

胡显伟 任世军

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