マンハッタンの距離は許容できるヒューリスティックではどうですか？

Question

1タイルの動きを数えると、他のタイルが目標状態になることはありますか？したがって、各タイルの数をカウントすると、目標状態に達するために必要な最小限の移動以上のカウントを得ることができます。

この質問は15パズルのマンハッタン距離の文脈にあります。ここで

は異なる単語での質問です：

我々はN-Puzzleの許容ヒューリスティックとしてマンハッタン距離を使用することができます。 A *検索を実装するには、許容可能なヒューリスティックが必要です。マンハッタンヒューリスティックは候補者ですか？はいの場合、上記の議論（質問の最初の3文）にどのように対処していますか？

説明：A*は検索アルゴリズムの一種です。ヒューリスティック関数を使用して、目標までの推定距離を決定します。このヒューリスティック関数がゴールまでの距離を過大評価することがない限り、アルゴリズムは最短経路を見つけます。おそらく、幅優先探索よりも高速です。その条件を満たすヒューリスティックは、許容可能です。

Answer 1

許容可能な経験則は、この問題を解決するための移動回数を過大評価してはなりません。一度に1つのブロックと4つの方向のうちの1つだけを移動することができるので、各ブロックの最適なシナリオは、ゴール状態への障害のない明確なパスを持つことです。これは1のM.D.

残りのブロックの状態は準最適であり、となります。は適切な場所でブロックを取得するためにM.D.より多くの動きをします。したがって、ヒューリスティックは決して過大評価されることはなく、許容される。

誰かがこれの正式な正式版を投稿したときに削除します。

Answer 2

正式証明： s *が目標状態である場合、h、h（s *）= 0の定義によって。 矛盾による証明のために、いくつかの初期状態s0についてC * < h（s0）と仮定する。各アクションは を1つのタイルだけ移動できるため、アクションを実行する場合は、最大でhを1減らすことができます。目標は のC *アクションに達することができるので、h（s *）≥h（s0）-C *> 0となるので、h（s *）はゼロでなければならないので、 の矛盾が生じます。したがって、 s0にはh（s0）≦C *が必要であり、hは許容される。 （ソース：カリフォルニア大学アーバイン）