gpt4 book ai didi

algorithm - 一致性启发式的证明意味着可接受的条件

转载 作者:行者123 更新时间:2023-12-05 04:57:09 27 4
gpt4 key购买 nike

我试图证明一致的启发式意味着可接受的条件

提到了我读过的一个证明 here :

  1. 设 h(n) 为节点 n 的启发式值,c(n,n+1) 为从节点 n 到节点 n+1 的成本。

  2. 假设 h(ng)=0;其中 ng 是目标节点。

  3. 通俗地说,我们想从目标节点回溯,表明如果我们从 h(ng)=0 的可接纳节点开始,则其父节点将通过一致性规则被接纳,并且模式继续。

  4. 考虑某个节点 n 并假设 n 处的启发式值是可接受的。

  5. 我们希望它的父节点,比如 n-1,也将符合一致性定义。

  6. 通过一致性,我们得到:

    h(n-1)-h(n)<=c(n-1,n)所以 h(n-1)<= c(n-1,n)+h(n)

  7. c(n-1,n) 是从 n-1 到 n 的实际路径成本。

  8. 因为我们知道 h(n) 是可接受的,所以我们知道 h(n) 必须小于或等于从 n 到 ng 的路径成本。

  9. 因此,h(n-1) <= 从 (n-1 到 n) + h(n) 的路径成本。

  10. 由于 h(n) 小于或等于从 (n 到 ng) 的路径成本,h(n-1) <= 从 (n-1 到 ng) 的路径成本。

我的问题是:在第 7 步中:c(n-1,n) 是从 n-1 到 n 的实际路径成本 他们如何确定 c(n-1,n ) 是实际路径吗?因为根据这个假设,他们所说的实际路径是成本最低的路径吗?

在同一个引用文献中,他们还给出了正式的证明:

  1. 假设我们有一些一致的启发式 h。还假设 h(ng)=0,其中 ng 是目标节点。

  2. 根据一致性的定义,图中所有节点 n 的 h(n)<=c(n,n+1)+h(n+1)。

  3. 我们想证明对于所有 n,h(n)<= h*(n)

  4. 基本情况:我们开始考虑 ng-1 任何路径中的节点,其中 ng 表示目标状态:

    h(ng-1)<=c(ng-1,ng)+h(ng)

  5. 因为ng是最好的目标状态,根据假设,h(ng)=h*(ng)

  6. 因此我们可以将上面的代码重写为:

    h(ng-1)<= c(ng-1,ng)+h*(ng)

  7. 鉴于此

    c(ng-1,ng)+h*(ng)=h*(ng-1)我们可以看到h(ng-1)<=h*(ng-1)

  8. 归纳假设:假设对于某个任意节点(位于目标路径上)ng-k 比 h(ng-k)<=h*(ng-k)。

  9. 归纳步骤:为了查看情况是否总是如此,我们考虑第 ng-k-1 次:

h(ng-k-1)<=c(ng-k-1,ng-k)+h(ng-k)
  1. 根据我们的基本案例,我们知道:
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)
  1. 我们再次知道:
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(ng'-1)<=c(ng'-1,g) + h(g) : h(g) =0 所以 h(ng'-1)<=c(ng'-1, g)

h(ng-1)<=c(ng-1,ng'-1) + h(ng'-1) 所以

h(ng-1)<=c(ng-1,ng'-1) +c(ng'-1,g)这是最优路径

对于任何具有更多节点数的最优路径也是正确的

关于algorithm - 一致性启发式的证明意味着可接受的条件,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/64596325/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com