给定一个启发式函数满足h(G)=0,其中G是目标状态，证明如果h是一致的，那么它是可采纳的。

问题

给定一个启发式函数满足h(G)=0,其中G是目标状态，证明如果h是一致的，那么它是可采纳的。

理解问题

要证明这个问题, 就需要理解三个问题

1. 什么是一致的?
2. 什么是可采纳的?
3. 如何将一致和可采纳联系起来?

节选自PPT的知识点

启发函数h(n)是可采纳的条件：

如果对于每个结点n, $h(n)<=h'(n)$，其中h*(n) 是到达目标结点的真实代价

一个启发函数是一致的条件：

对于任意一个结点n，以及n的行为a产生的后继结点n’,满足如下公式：

h(n) ≤ c(n,a,n’) + h(n’)

证明如下

假设 $n$为任意状态, $G$为某目标状态, 且 $n, N_1, N_2, ..., N_m, G$为从状态 $N$到达状态 $G$的一条最优路径.

已知 $h(n)$是一致的, 则满足
$h(n) \le c(n, a, n') + h(n')$

从 $n$到 $G$的评估函数为 $h(n)$

真实代价为
$h'(n) = c(n, a_1, N_1) + c(N_1, a_2, N_2) + \dots + c(N_m, a_{m+1}, G)$

根据可采纳条件, 要证明 $h(n)$是可采纳的, 就需要证明
$h(n) \le h'(n)$

则根据一致性条件
$\begin{aligned} h(n) &\le c(n, a_1, N_1) + h(N_1) \\ &\le c(n, a_1, N_1) + c(N_1, a_2, N_2) + h(N_2) \\ &\le c(n, a_1, N_1) + c(N_1, a_2, N_2)+ ... + c(N_m, a_{m+1}, G) + h(G) \\ &= c(n, a_1, N_1) + c(N_1, a_2, N_2)+ ... + c(N_m, a_{m+1}, G) \\ &= h'(n) \end{aligned}$
因此 $h(n) <=h'(n)$得证, 即如果 $h(n)$是一致的, 那么它是可采纳的.

转载：https://blog.csdn.net/wjh2622075127/article/details/101981573