线性可采纳搜索算法的充要条件

The Sufficient and Necessary Condition of Linear Admissible Search Algorithms

针对图搜索问题,本文证明了任一可采纳搜索算法Г维持其复杂度为O(N)(N是解路径的长度)的充分必要条件是,算法Г使用的启发估计函数h_г(·)满足其中B、C是常数,θ(x)是满足limθ(x)=0的可微函数,是由θ(x)定义的函数。

About the search problem of artificial intelligence, it is proved an admissible algorithm Γ is linear if and only if the estimate function used by Γ satisfies where B,C are constants, θ(x) is an arbitrary differentiable function of x with limθ(x)=θ,φ^(-1)(x) is a function of θ(x). The conclusion provides a goal to the “learning”of a new kind research which is called LEARNING SEARCH.