启发式搜索中启发函数的可容许性与一致性启发式的理解

前言

启发式搜索(Heuristically Search)又称为有信息搜索(Informed Search)，它是利用问题拥有的启发信息来引导搜索，达到减少搜索范围、降低问题复杂度的目的，这种利用启发信息的搜索过程称为启发式搜索。

启发式搜索的评价函数一般为：
$$f(n)=g(n)+h(n)$$
其中$g(n)$为初始状态到达n状态的已发生的路径代价，$h(n)$​为启发函数，估计了从n状态到goal状态的代价。

启发式算法的关键点在于如何构造启发函数，这是一个难点。为了让算法的性能优越，往往我们需要考虑让启发式函数符合两个特性——可容许性（admissible）和一致性（consistency），本文介绍一些关于该二者的个人理解。

一、可容许性启发式

可容许性定义：

一个可容许的启发函数h(n)要求$，h(n)<=n到goal的实际最小代价$​，即永远不高估到目标的代价。因此f(n)实际上是，以初始状态到n的这条路径为前半段，再从n到目标状态的代价的下界。

可容许性特点：

可容许性启发式的搜索算法一定能找到最优解，因为其永远搜素那些待扩展点中$f(n)$​最小的节点，从直观上来看：对任意一个在某条最优路径上的状态，（由启发式定义可知）满足$f(n)=g(n)+h(n)<=C^{\ast }（C\ast 为最优路径代价）$，而非最优路径上，一定存在一状态点使得$g(n)+h(n)>C^{\ast }$,（至少在goal这点绝对成立，因为此时h(goal)=0,而g(goal)即为该路径代价，该路径为非最优路径显然$g(n)>C^{\ast }$）,因此只要有一个最优路径上的点被搜索过了（容易想象初始点的扩展点中一定存在最优路径上的点，因为所有路径至少经过其中某个点），那么这些$f(n)>C^{\ast }$的点将永远不会被选中，因为每次只选择f(n)最小的点，而最优路径上的点的扩展（后继）点中一定还有最优路径上的点，因此那些$f(n)>C^{\ast }$的待扩展状态点永远不会有最小的f(n)。所以可容许性启发式永远不会返回非最优路径。

形式化的证明：

假设该算法返回了一条非最优路径，那么该路径的代价C>C*,（C*为最优路径代价）那么一定存在一个最优路径上的状态$x$未被扩展，则有：
$$\begin{array}{rlrl}& f(x)>C\ast & & (根据假设得到，否则x将是已扩展节点)\\ & f(x)=g^{\ast }(x)+h(x)& & (g^{\ast }(x)表示通过最优路径到达x节点的代价)\\ & f(x)\le g^{\ast }(x)+h^{\ast }(x)& & (可容许性，h(x)\le h^{\ast }(x))\\ & f(x)\le C^{\ast }& & (C^{\ast }=g^{\ast }(x)+h^{\ast }(x))\end{array}$$
由此与假设矛盾，因此该算法一定返回一条最优路径。

二、一致性启发式

一致性定义

一致性要求:$h(n)<=c(n,a,n^{\prime })+h(n^{\prime }),c(n,a,n^{\prime })表示n到其后继点n^{\prime }的代价$。

一致性性特点：

很容易知道满足一致性一定满足可容许性，此外一致性有以下特点：

由此$f(n)=g(n)+h(n)<=f(n^{\prime })+=g(n^{\prime })+h(n^{\prime }）=g(n)+c(n,a,n^{\prime })+h(n^{\prime })$​，可见f(n)是随n搜索层次增大不断增大的一个函数。因此在不断选择的过程中，那些待扩展的点的f(n)的下界不断增大，用数学的话来说，即这些待扩展的点的f(n)在一致地增大，由此最终待扩展点的f(n)会一致地趋近于C*，直到找到最优路径。

三、总结

所以我们可以直观地得到一致性比可容许性更强的原因：在二者中，只要那些满足$f(n)=g(n)+h(n)<=C^{\ast }$的点都会被搜索，在可容许性启发式中，不管该点在搜索层次上多靠后都没有某种约束限制其$f(n)<C^{\ast }$的可能性，而在一致性启发式中由于f(n)随搜索层次递增，因此$f(n)<C^{\ast }$​的可能性也随搜索层次的增加而减小，从而将许多不必要的状态排除在外。

一致性的启发式其一致收敛性保证了这种启发搜索相较于其他搜索一定是最高效的，且是完备的、代价最优的，而可容许性仅能保证是完备、代价最优的。

注：完备性指对搜索问题一定能找到解或者指出无解，代价最优指找到的解是代价最小的路径。