一致性启发式的证明意味着可接受的条件
Proof of consistent heuristic implies admissible condition
我试图证明一致的启发式意味着可接受的条件
提到了我读过的一个校样here:
设 h(n) 为节点 n 处的启发值，c(n,n+1) 为从节点 n 到节点 n+1 的成本。
我们假设h(ng)=0；其中 ng 是目标节点。
通俗地说，我们想从目标节点回溯表明，如果我们从 h(ng)=0 的可接纳节点开始，则其父节点将通过一致性规则被接纳，并且模式继续。
考虑某个节点 n 并假设 n 处的启发式值是可接受的。
我们希望它的父节点，比如 n-1，也将被一致性定义所接受。
通过一致性，我们得到：
h(n-1)-h(n)<=c(n-1,n)
所以 h(n-1)<= c(n-1,n)+h(n)
c(n-1,n)是从n-1到n的实际路径成本。
因为我们知道 h(n) 是可接受的，所以我们知道 h(n) 必须小于或等于从 n 到 ng 的路径成本。
因此，h(n-1) <= 从 (n-1 到 n) + h(n) 的路径成本。
由于 h(n) 小于或等于从 (n 到 ng) 的路径成本，h(n-1) <= 从 (n-1 到 ng) 的路径成本。
我的问题是：在第 7 步中：c(n-1,n) 是从 n-1 到 n 的实际路径成本 他们如何确定 c( n-1,n) 是实际路径吗？因为根据这个假设，他们所说的实际路径是成本最低的路径？
在同一个参考文献中他们也给出了正式的证明：
假设我们有一些一致的启发式 h。还假设 h(ng)=0，其中 ng 是目标节点。
根据一致性的定义，对于图中的所有节点 n，h(n)<=c(n,n+1)+h(n+1)。
我们要证明对于所有 n，h(n)<= h*(n)
基本情况：我们开始考虑 ng-1 任何路径中的节点，其中 ng 表示目标状态：
h(ng-1)<=c(ng-1,ng)+h(ng)
因为ng是最好的目标状态，根据假设，h(ng)=h*(ng)
因此我们可以将上面的代码重写为：
h(ng-1)<= c(ng-1,ng)+h*(ng)
并且鉴于
c(ng-1,ng)+h*(ng)=h*(ng-1)
我们可以看到
h(ng-1)<=h*(ng-1)
归纳假设：假设对于某个任意节点（位于目标路径上）ng-k 比 h(ng-k)<=h*(ng-k).
归纳步骤：看是否总是这样，我们考虑第ng-k-1次：
h(ng-k-1)<=c(ng-k-1,ng-k)+h(ng-k)
- 根据我们的基本案例，我们知道：
h(ng-k-1)<=c(ng-k-1,ng-k)+h(ng-k)<= c(ng-k-1,ng-k)+h*(ng-k)
h(ng-k-1)<=c(ng-k-1,ng-k)+h*(ng-k)
- 我们再次知道：
h(ng-k-1,ng-k)+h*(ng-k)=h*(ng-k-1)
so we can see :
h(ng-k-1)<=h*(ng-k-1)
同样是第8步和第12步的问题，为什么要考虑：c(本节点，下一个节点) + h*(下一个节点) = h*(本节点)？
我能够证明：
c(ng-1,ng)+h*(ng)=h*(ng-1) 我们可以说 h(ng-1)<=h*(ng-1)
如果 c(ng-1,ng) 不是从 ng-1 到目标的最佳路径，我们假设从 ng-1 到 ng'-1 到 g 有另一条路径是最佳路径所以：
ng-1 --> ng'-1 --> g是最佳路径
因为h是一致的：
h(of'-1)<=c(of'-1,g) + h(g) : h(g) =0 所以 h(of'-1)<=c(of'- 1,g)
h(of-1)<=c(of-1,of'-1) + h(of'-1) 所以
h(ng-1)<=c(ng-1,ng'-1) +c(ng'-1,g)这是最佳路径
对于具有更多节点数的任何最佳路径也是正确的
我试图证明一致的启发式意味着可接受的条件
提到了我读过的一个校样here:
设 h(n) 为节点 n 处的启发值，c(n,n+1) 为从节点 n 到节点 n+1 的成本。
我们假设h(ng)=0；其中 ng 是目标节点。
通俗地说，我们想从目标节点回溯表明，如果我们从 h(ng)=0 的可接纳节点开始，则其父节点将通过一致性规则被接纳，并且模式继续。
考虑某个节点 n 并假设 n 处的启发式值是可接受的。
我们希望它的父节点，比如 n-1，也将被一致性定义所接受。
通过一致性，我们得到：
h(n-1)-h(n)<=c(n-1,n) 所以 h(n-1)<= c(n-1,n)+h(n)
c(n-1,n)是从n-1到n的实际路径成本。
因为我们知道 h(n) 是可接受的，所以我们知道 h(n) 必须小于或等于从 n 到 ng 的路径成本。
因此，h(n-1) <= 从 (n-1 到 n) + h(n) 的路径成本。
由于 h(n) 小于或等于从 (n 到 ng) 的路径成本，h(n-1) <= 从 (n-1 到 ng) 的路径成本。
我的问题是：在第 7 步中：c(n-1,n) 是从 n-1 到 n 的实际路径成本 他们如何确定 c( n-1,n) 是实际路径吗？因为根据这个假设，他们所说的实际路径是成本最低的路径？
在同一个参考文献中他们也给出了正式的证明：
假设我们有一些一致的启发式 h。还假设 h(ng)=0，其中 ng 是目标节点。
根据一致性的定义，对于图中的所有节点 n，h(n)<=c(n,n+1)+h(n+1)。
我们要证明对于所有 n，h(n)<= h*(n)
基本情况：我们开始考虑 ng-1 任何路径中的节点，其中 ng 表示目标状态：
h(ng-1)<=c(ng-1,ng)+h(ng)
因为ng是最好的目标状态，根据假设，h(ng)=h*(ng)
因此我们可以将上面的代码重写为：
h(ng-1)<= c(ng-1,ng)+h*(ng)
并且鉴于
c(ng-1,ng)+h*(ng)=h*(ng-1) 我们可以看到 h(ng-1)<=h*(ng-1)
归纳假设：假设对于某个任意节点（位于目标路径上）ng-k 比 h(ng-k)<=h*(ng-k).
归纳步骤：看是否总是这样，我们考虑第ng-k-1次：
h(ng-k-1)<=c(ng-k-1,ng-k)+h(ng-k)
- 根据我们的基本案例，我们知道：
h(ng-k-1)<=c(ng-k-1,ng-k)+h(ng-k)<= c(ng-k-1,ng-k)+h*(ng-k)
h(ng-k-1)<=c(ng-k-1,ng-k)+h*(ng-k)
- 我们再次知道：
h(ng-k-1,ng-k)+h*(ng-k)=h*(ng-k-1)
so we can see :
h(ng-k-1)<=h*(ng-k-1)
同样是第8步和第12步的问题，为什么要考虑：c(本节点，下一个节点) + h*(下一个节点) = h*(本节点)？
我能够证明：
c(ng-1,ng)+h*(ng)=h*(ng-1) 我们可以说 h(ng-1)<=h*(ng-1)
如果 c(ng-1,ng) 不是从 ng-1 到目标的最佳路径，我们假设从 ng-1 到 ng'-1 到 g 有另一条路径是最佳路径所以：
ng-1 --> ng'-1 --> g是最佳路径
因为h是一致的：
h(of'-1)<=c(of'-1,g) + h(g) : h(g) =0 所以 h(of'-1)<=c(of'- 1,g)
h(of-1)<=c(of-1,of'-1) + h(of'-1) 所以
h(ng-1)<=c(ng-1,ng'-1) +c(ng'-1,g)这是最佳路径
对于具有更多节点数的任何最佳路径也是正确的