高阶Hopfield神经网求解合取范式可满足性问题

HIGH-ORDER HOPFIELD NETWORK FOR SAT

本文提出用高阶Hopfield神经网络求解SAT问题，给出了连续及离散高阶神经网络模型与相应的离散快速求解算法，证明了网络的稳定性．并用实验证明了该方法的可行性，且将该算法与LocalSearch算法进行了比较．

The CNFSAT Problem is an NP-Comlete Problem. Inengineering mnyappications can be mapped into SAT Problems. So designing a fast and efficientalgorithm for solving SAT probems is valuabe. The Hopeld netWork as a classicalneural network has been widely appied in the optindzation field.In thes paper,anew mpthod tha appies the highother Hopeld neuIal network to solve the SAT problem is Presented and the thought how to map the SAT Problem into the Hopfieldnetwork is discussed in detail. The definihon of the networks. enerpy hahon isgiven and the networks' constructing method (including continuous and discretemodl) are presented. This paper also proves the networks' stahility and discussesthe strategies about how to escape from local minimal points in the network. Final-ly simulating experiments in which the discrete Hop field network is adopted aredone to solve the 3-SAT problem and their results compared with the classical localsearch algorithm are presented. It proves that the algorithm is fast and efficient,especially the number of searching is decreased prominently.