algorithm - 互換性のあるヒューリスティックが A* 検索アルゴリズムで許容できるヒューリスティックであることを証明する方法

Question

互換性のあるヒューリスティック (h) は、以下の条件を持つものです。

h(n) <= c(n,a,n') + h(n')

****************************************************

許容ヒューリスティック (h) は、以下の条件を持つものです。

0 <= h(n) <= h*(n)

h*(n) は、ノードからノードnまでの実際の距離です。goal

ヒューリスティックに互換性がある場合、それが許容できることをどのように証明しますか?

どうもありがとう。

Answer 1

h に追加の条件 (つまり、h(goal) = 0) を追加すると、n からゴール状態への最小コスト パスの帰納法によって証明できます。

基本ケースでは、n = ゴールの場合、最小コスト パスは 0 です。次に、h(ゴール) = 0 = h*(ゴール) です。

一般的なケースでは、n をノードとし、n' を n からゴールまでの最小パス上の次のノードとします。次に、帰納法仮説を使用して最初の不等式と秒の互換性の定義。