集合覆盖问题的启发函数算法  

A Heuristic Function Algorithm for Minimum Set covering Problem

作　　者：权光日[1] 洪炳熔[1] 叶风[1] 任世军[1] 

机构地区：[1]哈尔滨工业大学计算机科学与工程系

出　　处：《软件学报》1998年第2期156-160,共5页Journal of Software

基　　金：国防科工委"九五"攻关项目基金

摘　　要：本文给出了求解ＮＰ困难问题的完备策略的概念，在此基础上提出了一个求解集合覆盖问题的启发函数算法ＳＣＨＦ（ｓｅｔ－ｃｏｖｅｒｉｎｇｈｅｕｒｉｓｔｉｃｆｕｎｃｔｉｏｎ），文中对该算法的合理性、时间复杂性以及解的精度进行了分析，本文的主要创新点是用已知的完备策略建立启发函数，并用该启发函数进行空间搜索求出优化解．该方法具有一定的普遍性，可以应用到其它的ＮＰ困难问题．它为求解ＮＰ困难问题的近似解提供了一种行之有效的方法．在规则学习中的应用结果表明，本文给出的ＳＣＨＦ算法是非常有效的．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.

关 键 词：集合覆盖 启发函数 算法 NP问题 

分 类 号：O22[理学—运筹学与控制论]