1 つのタイルの移動をカウントしている間に、他のタイルが目標状態に到達する可能性があるというのは本当ですか? したがって、各タイルをカウントすると、目標状態に到達するために必要な最小移動数よりも多くのカウントが得られる可能性がありますか?
この質問は、15 パズルのマンハッタン距離に関連しています。
異なる言葉での質問は次のとおりです。
マンハッタン距離を N-Puzzle の許容可能なヒューリスティックとして使用できますか? A* 検索を実装するには、許容できるヒューリスティックが必要です。マンハッタンヒューリスティックは候補ですか？はいの場合、上記の議論 (質問の最初の 3 つの文) にどのように反論しますか?
定義: A*は検索アルゴリズムの一種です。ヒューリスティック関数を使用して、ゴールまでの推定距離を決定します。このヒューリスティック関数がゴールまでの距離を過大評価しない限り、アルゴリズムはおそらく幅優先探索よりも速く最短経路を見つけます。その条件を満たすヒューリスティックは許容されます。
この問題を解決するために許容されるヒューリスティックスでは、移動回数を過大評価してはなりません。ブロックは一度に 1 つしか移動できず、4 つの方向のうちの 1 つにしか移動できないため、各ブロックの最適なシナリオは、目標状態への明確で遮るもののないパスがあることです。これは 1 の MD です。
ブロックのペアの残りの状態は最適ではありません。つまり、ブロックを適切な場所に配置するには、MD よりも多くの移動が必要になります。したがって、ヒューリスティックは決して過大評価せず、許容されます。
誰かがこれの正確で正式なバージョンを投稿したら削除します.
形式的証明: h の定義により、s∗ が目標状態の場合、h(s∗) = 0 です。矛盾による証明のために、ある初期状態 s0 に対して C∗ < h(s0) であると仮定します。各アクションで移動できるタイルは 1 つだけなので、アクションを実行すると h が最大で 1 つ減ることに注意してください。C* のアクションでゴールに到達できるので、h(s*) ≥ h(s0) − C* > 0 となり、h(s*) はゼロでなければならないという矛盾が生じます。したがって、すべての s0 に対して h(s0) ≤ C∗ を持たなければならず、h は許容されます。（出典：カリフォルニア大学アーバイン校）