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

发布时间：2024-12-17 02:15

爸爸教女儿弹钢琴，女儿抱怨说：‘琴键都一样，怎么知道哪个是A，哪个是G？’爸爸：‘就像人生，每个困难都是一个音符，只要用心感受，就能找到它们的位置。’ #生活乐趣# #日常生活趣事# #日常生活笑话# #家庭笑料#

问题

理解问题

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

什么是一致的?什么是可采纳的?如何将一致和可采纳联系起来? 节选自PPT的知识点

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

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

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

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

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

在这里插入图片描述

证明如下

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

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

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

真实代价为
h ′ ( n ) = c ( n , a 1 , N 1 ) + c ( N 1 , a 2 , N 2 ) + ⋯ + c ( N m , a m + 1 , G ) 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)=c(n,a1,N1)+c(N1,a2,N2)+⋯+c(Nm,am+1,G)

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

则根据一致性条件
h ( n ) ≤ c ( n , a 1 , N 1 ) + h ( N 1 ) ≤ c ( n , a 1 , N 1 ) + c ( N 1 , a 2 , N 2 ) + h ( N 2 ) ≤ 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 ) h(n)≤c(n,a1,N1)+h(N1)≤c(n,a1,N1)+c(N1,a2,N2)+h(N2)≤c(n,a1,N1)+c(N1,a2,N2)+...+c(Nm,am+1,G)+h(G)=c(n,a1,N1)+c(N1,a2,N2)+...+c(Nm,am+1,G)=h′(n)

h(n)≤c(n,a1,N1)+h(N1)≤c(n,a1,N1)+c(N1,a2,N2)+h(N2)≤c(n,a1,N1)+c(N1,a2,N2)+...+c(Nm,am+1,G)+h(G)=c(n,a1,N1)+c(N1,a2,N2)+...+c(Nm,am+1,G)=h′(n)
因此 h ( n ) < = h ′ ( n ) h(n) <=h'(n) h(n)<=h′(n)得证, 即如果 h ( n ) h(n) h(n)是一致的, 那么它是可采纳的.

网址：给定一个启发式函数满足h(G)=0,其中G是目标状态，证明如果h是一致的，那么它是可采纳的。 https://www.yuejiaxmz.com/news/view/493065

上一篇: 旧房厨房如何改造改造方案速来看

下一篇: 观察下列表格：请你结合该表格及相

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

问题

理解问题

证明如下

相关内容

随便看看

最新动态分享

热点动态分享

专题

推荐动态分享