一种新的求解集合覆盖问题的启发式算法  

A New Heuristic Algorithm for Set Covering Problem

作　　者：权光日[1] 洪炳熔[1] 叶风[1] 吴葳[1] 

机构地区：[1]哈尔滨工业大学计算机系智能机器人研究室

出　　处：《哈尔滨工业大学学报》1998年第5期38-41,共4页Journal of Harbin Institute of Technology

摘　　要：给出了一种新的求解集合覆盖问题的新的启发式算法，对该算法的合理性、时间复杂性以及解的精度进行了分析，主要创新点是用完备策略建立启发式算法．该方法具有一定的普遍性，可以应用到其它的ＮＰ困难问题．本算法应用到规则学习问题建立了新的规则学习算法，示例分析表明了该算法的有效性．The rationality, the time complexity and the precision of the solution is discussed for the heuristic algorithm for the set covering problem. The basic idea is to structure the heuristic algorithm by the given complete strategy. This method can be applied to other NP hard problems. As an application of the algorithm, this paper presents a new algorithm of learning from examples.

关 键 词：启发式算法 完备策略 NP问题 集合覆盖问题 

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