首页 | 本学科首页   官方微博 | 高级检索  
     检索      

求解最优可满足性问题的算法设计
引用本文:李聪睿.求解最优可满足性问题的算法设计[J].湛江师范学院学报,2011,32(6):43-46.
作者姓名:李聪睿
作者单位:湛江师范学院基础教育学院数学系,广东湛江,524037
摘    要:最优可满足性问题是一类典型的NP完全问题,该文提出一个基于离散问题连续化转换的拟物思想,求解转化为CNF范式的最优可满足性问题的算法,使得关于CNF范式取真的充要条件转化为连续函数的f(x珟)=0.设计的算法来源于物理模型;在映射变换的过程中充分利用了连续性以及改进的梯度算法.该算法简便、实用,而且以最小码覆盖问题为例,对该算法进行了实际的设计与分析.

关 键 词:最优可满足性问题  算法设计  CNF范式

Design of Algorithm for Optimum Satisfiability Problems
LI Congrui.Design of Algorithm for Optimum Satisfiability Problems[J].Journal of Zhanjiang Normal College,2011,32(6):43-46.
Authors:LI Congrui
Institution:LI Congrui(Department of Mathematics,Basic Education College of Zhanjiang Normal University, Zhanjiang 524037,Guangdong,China)
Abstract: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.
Keywords:optimum satisfiability problem  design of algorithm  CNF form
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号