A New Algorithm for Solving SAT Problems based on Function Transformation
HU Xianwei · Intelligent Computer and Applications · 2012
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.