| 摘要: |
| 本文给出了求解NP困难问题的完备策略的概念,在此基础上提出了一个求解集合覆盖问题的启发函数算法SCHF(set-covering heuristic function),文中对该算法的合理性、时间复杂性以及解的精度进行了分析,本文的主要创新点是用已知的完备策略建立启发函数,并用该启发函数进行空间搜索求出优化解.该方法具有一定的普遍性,可以应用到其它的NP困难问题.它为求解NP困难问题的近似解提供了一种行之有效的方法.在规则学习中的应用结果表明,本文给出的SCHF算法是非常有效的. |
| 关键词: 启发函数,完备策略,示例学习,NP困难问题. |
| DOI： |
| 分类号: |
| 基金项目:本文研究得到国防科工委“九五”攻关项目基金资助. |
|
| A Heuristic Function Algorithm for Minimum Set-covering Problem |
|
QUAN Guang-ri,HONG Bing-rong,YE feng,REN Shi-jun
|
| Abstract: |
| 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. |
| Key words: Heuristic function, complete strategy, learning from examples, NP hard problem. |
