求解最优可满足性问题的算法设计

Design of Algorithm for Optimum Satisfiability Problems

最优可满足性问题是一类典型的NP完全问题,该文提出一个基于离散问题连续化转换的拟物思想,求解转化为CNF范式的最优可满足性问题的算法,使得关于CNF范式取真的充要条件转化为连续函数的f(x珟)=0.设计的算法来源于物理模型;在映射变换的过程中充分利用了连续性以及改进的梯度算法.该算法简便、实用,而且以最小码覆盖问题为例,对该算法进行了实际的设计与分析.

Optimun Satisfiability problem is a canonical NP problem.In this Paper,we present a new algorithm for Optimum Satisfiability problem which can be turned into CNF form.The algorithm bases on the quasi-physical ideas of turning the discrete problem into continuous function.Then the optimum Satisfiability problem becomes the problem which CNF form is true if and only if the continuous function is zero.The idea of the algorithm comes from physical model.In the map turning,it uses continuous and improved gradient algorithm.The new algorithm is easy and fast.In the end,an example on minimal code problem is used to test the algorithm.