Probably Approximately Correct Heuristic Search

摘要: A* is a best-first search algorithm that returns an optimal solution. w-admissible algorithms guarantee the returned solution no larger than w times In this paper we introduce generalization of w-admissibility concept call PAC search, which inspired by learning framework in Machine Learning. The task to find with high probability. formally define and present for can work on top any produces sequence solutions. Experimental results 15-puzzle demonstrate our activated Anytime Weighted (AWA*) expands significantly less nodes regular AWA* while returning solutions have almost same quality.