| 集合覆盖问题的启发函数算法 |
| |
| 引用本文： | 权光日,洪炳熔,叶 风,任世军.集合覆盖问题的启发函数算法[J].软件学报,1998,9(2):156-160. |
| |
| 作者姓名： | 权光日 洪炳熔 叶 风 任世军 |
| |
| 作者单位： | 哈尔滨工业大学计算机科学与工程系,哈尔滨,150001;哈尔滨工业大学计算机科学与工程系,哈尔滨,150001;哈尔滨工业大学计算机科学与工程系,哈尔滨,150001;哈尔滨工业大学计算机科学与工程系,哈尔滨,150001 |
| |
| 基金项目： | 本文研究得到国防科工委“九五”攻关项目基金资助. |
| |
| 摘 要： | 本文给出了求解NP困难问题的完备策略的概念,在此基础上提出了一个求解集合覆盖问题的启发函数算法SCHF(set-covering heuristic function),文中对该算法的合理性、时间复杂性以及解的精度进行了分析,本文的主要创新点是用已知的完备策略建立启发函数,并用该启发函数进行空间搜索求出优化解.该方法具有一定的普遍性,可以应用到其它的NP困难问题.它为求解NP困难问题的近似解提供了一种行之有效的方法.在规则学习中的应用结果表明,本文给出的SCHF算法是非常有效的.
|
| 关 键 词： | 启发函数 完备策略 示例学习 NP困难问题. |
| 收稿时间： | 1996/10/3 0:00:00 |
| 修稿时间： | 1997/11/20 0:00:00 |
A Heuristic Function Algorithm for Minimum Set-covering Problem |
| |
| QUAN Guang-ri,HONG Bing-rong,YE feng and REN Shi-jun.A Heuristic Function Algorithm for Minimum Set-covering Problem[J].Journal of Software,1998,9(2):156-160. |
| |
| Authors: | QUAN Guang-ri HONG Bing-rong YE feng and REN Shi-jun |
| |
| Affiliation: | Department of Computer Science and Engineering\ Harbin Institute of Technology\ Harbin\ 150001 |
| |
| 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. |
| |
| Keywords: | Heuristic function complete strategy learning from examples NP hard problem |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
