未找到相关数据
集合覆盖问题的启发函数算法
被引：15
作者：
权光日
洪炳熔
叶风
任世军
机构：
[1] 哈尔滨工业大学计算机科学与工程系
来源：
基金：
“九五”攻关项目;
关键词：
启发函数，完备策略，示例学习，NP困难问题;
D O I：
10.13328/j.cnki.jos.1998.02.016
中图分类号：
TP301.6, [];
学科分类号：
摘要：
本文给出了求解ＮＰ困难问题的完备策略的概念，在此基础上提出了一个求解集合覆盖问题的启发函数算法ＳＣＨＦ（ｓｅｔ－ｃｏｖｅｒｉｎｇｈｅｕｒｉｓｔｉｃｆｕｎｃｔｉｏｎ），文中对该算法的合理性、时间复杂性以及解的精度进行了分析，本文的主要创新点是用已知的完备策略建立启发函数，并用该启发函数进行空间搜索求出优化解．该方法具有一定的普遍性，可以应用到其它的ＮＰ困难问题．它为求解ＮＰ困难问题的近似解提供了一种行之有效的方法．在规则学习中的应用结果表明，本文给出的ＳＣＨＦ算法是非常有效的．
引用
收藏
页码：77 / 81
页数：5
相关论文