摘要
归纳学习的扩张矩阵方法中,在一个反例集NE背景下求一个正例e^+的最短公式问题(MFL)和在NE背景下求一个正例集PE的最优覆盖问题(MCV)是两个突出的最优化问题.文献[1]业已证明它们均为NP-hard的.本文给出作者设计的四个算法,分别称之为MFL,HFL,MCV和HCV.算法MFL和MCV是完备算法,它们分别为MFL问题和MCV问题提供了关于例子空间属性数的指数时间、例子数的多项式时间的求解方法.算法HFL和HCV是两个分别对应于算法MFL和MCV但时间复杂性为多项式的启发式算法.
出处
《中国科学（A辑）》
CSCD
1992年第2期200-207,共8页
Science in China(Series A)
基金
国家自然科学基金
