Polynomial Approximation Based Learning Search
基于函数逼近的学习式搜索

In this paper, Polynomial Approximation method and theory are introduced into the research of Learning Search of Artificial Intelligence. In this way, we can 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 setrch algorithms, A-Bn, is presented and it is shown that, when the number of training samples becomes large enough, the worst-case complexity of A-B, can be reduced to O(poly(N)), where N is the length of the optimal solution path, poly (N) is a polynomial of N.