摘要
本文给出了求解NP困难问题的完备策略的概念,在此基础上提出了一个求解集合覆盖问题的启发函数算法SCHF(set-coveringheuristicfunction),文中对该算法的合理性、时间复杂性以及解的精度进行了分析,本文的主要创新点是用已知的完备策略建立启发函数,并用该启发函数进行空间搜索求出优化解.该方法具有一定的普遍性,可以应用到其它的NP困难问题.它为求解NP困难问题的近似解提供了一种行之有效的方法.在规则学习中的应用结果表明,本文给出的SCHF算法是非常有效的.
In this paper, an algorithm based on heuristic function for minimum set covering problem is presented, as well as the definition of complete strategy concept and the method to structure heuristic function. The rationality, the time complexity and the precision of the solution are discussed for the algorithm. The basic idea is to structure heuristic function with the given heuristic strategies. The method can apply to other NP hard problems. As application of the algorithm, this paper presents a new algorithm of learning rule from the examples based on heuristic function.
出处
《软件学报》
EI
CSCD
北大核心
1998年第2期156-160,共5页
Journal of Software
基金
国防科工委"九五"攻关项目基金
关键词
集合覆盖
启发函数
算法
NP问题
Heuristic function, complete strategy, learning from examples, NP hard problem. Class number\ TP301.6