Abstract: 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.