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

作者：李聪睿

来源：湛江师范学院学报, 2011, (06): 43-46.

• 最优可满足性问题
• 算法设计
• CNF范式 optimum satisfiability problem
• design of algorithm
• CNF form

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

• 单位
  湛江师范学院基础教育学院