可满足性问题的填充函数算法  

A filled function method for satisfiability problem

作　　者：林耿[1] 

机构地区：[1]闽江学院数学系,福建福州350108

出　　处：《闽江学院学报》2011年第2期12-15,共4页Journal of Minjiang University

基　　金：闽江学院育苗项目(YKY1012)

摘　　要：可满足性问题是第一个被证明为NP-complete问题.首先给出两个解之间距离的概念,其次构造出一类单参数填充函数,该函数形式简洁,便于计算.然后,针对可满足性问题提出了一类填充函数算法,实验表明该算法是有效的.Satisfiability problem is firstly proved to be an NP-complete problem.Firstly,this paper defines a concept of the distance between two solutions.Next,a filled function with only one parameter is constructed,it is simple and easy to calculate.Then a filled function method for satisfiability problem is proposed,numerical results show that the proposed algorithm is efficient.

关 键 词：可满足性问题 填充函数 启发式 

分 类 号：O211.63[理学—概率论与数理统计]