|
|||||
|
|
| 扩张矩阵的最优化问题 | |
| 作者姓名： | 吴信东 |
| 作者单位： | 合肥工业大学计算机与信息系 合肥 230009 |
| 摘 要： | 归纳学习的扩张矩阵方法中,在一个反例集NE背景下求一个正例e~+的最短公式问题(MFL)和在NE背景下求一个正例集PE的最优覆盖问题(MCV)是两个突出的最优化问题.文献[1]业已证明它们均为NP-hard的.本文给出作者设计的四个算法,分别称之为MFL,HFL,MCV和HCV.算法MFL和MCV是完备算法,它们分别为MFL问题和MCV问题提供了关于例子空间属性数的指数时间、例子数的多项式时间的求解方法.算法HFL和HCV是两个分别对应于算法MFL和MCV但时间复杂性为多项式的启发式算法. |
| 关 键 词： | 归纳学习 扩张矩阵 最优化 NP难题 多项式时间 |
| 点击此处可从《中国科学A辑》浏览原始摘要信息 | |
| 点击此处可从《中国科学A辑》下载免费的PDF全文 | |