作　　者： ;

机构地区： 辽宁大学信息学院计算机科学与技术系

出　　处： 《辽宁大学学报（自然科学版）》 1995年第A00期113-116,122,共5页

摘　　要： 本文将多项式逼近的方法引入到学习式搜索中，使学习式搜索通过一定数量的解题训练后可以建立起一个任意一致逼近理想函数ｈ（·）的启发估计函数ｈ（·）．本文给出了一个这样的学习式搜索算法Ａ－Ｂｎ，并证明了当训练例子集充分大后，Ａ－Ｂｎ可在多项式复杂度内解决任一后来提交的同类问题． In this paper, Polynomial Approximation method and theory areintroduced into the rescarch of Learning Search of Artificial Intelligence. In this way,wecan use a search algorithm repeatedly to construct a heuristic estimate function h(.)which uniformly approximates to the optimal estimate function h(.)with arbitrarily high precision. One of such learning search algorithms,A-Bn,ispresented and it is shown that, when the number of training samples becomes largeenough,the worst-case complexity of A-Bn can be reduced to O(poly(N)),where Nis the length of the optimal solution path,poly(N) is a ploymomial of N.

关 键 词： 复杂度 多项式逼近 学习式搜索 函数逼近

领　　域： [理学] [理学]