A *アルゴリズムのヒューリスティックが許容できないのはなぜですか？

Question

私はCS188を公開し、edx.orgにアクセスしています。今、私はここに示すように、すべてのペレットを食べるためにA *探索のためのヒューリスティックを開発する必要があります。

私は（許容し、一貫性の両方として）、仕事と確信していた私のヒューリスティックは、次のように行ってきました：

• は、ペレットが食べていないが0
• はパックマン
• の現在位置とPOSを初期化することが時間と呼ばれるヒューリスティックアキュムレータを初期化：
  • ASTAR検索（ヒューリスティックとしてマンハッタン距離）
  • を使用して、POSから最も近いペレットをペレット

の位置であることをペレット

セットPOSからペレットを除去し、H

までの距離を追加します

私はまた、以前に計算された距離をキャッシュするので、最も近いペレットを見つけるためのastar探索は、前に状態の別の計算で前に行われていれば完了しません。問題を非常に迅速に解決することができ、結果は最適です。

このアルゴリズムをオートグラードで使用すると、許容性テストに失敗します。

問題の解決方法を求めているわけではありません。私の現在の解決策はなぜ受け入れられないのですか？私の頭の中の絵の例を見ると、ヒューリスティックはコストを過大評価することはありません。

誰もがこれを理解することができ、あなたの意見が大変ありがとうございました。

Answer 1

A *のヒューリスティックは、可能な限り最高のコストである必要があります。ヒューリスティックは、これを保証しない、妥当な貪欲な解決策です。一列のペレットがあり、パク・マンがこのラインの中心からわずかに離れているとします。最も安い解決策は、ラインの終わりが最も近いものであり、そのラインの終わりまでペレットをすべて食べ、次に他のペレットを食べるために他のペレットを移動させることです。

あなたの貪欲なヒューリスティックスは、最短距離を持つ側ではない可能性のあるペックマンに最も近いペレットに最初に移動します。この場合、最適なコストを超えないコストが返される可能性があります。最適ではない可能性のある解決策のコスト。

Answer 2

ここでは、問題に適したヒューリスティックを設定する方法を示します。まず、あなたの目標が最小距離ですべてのペレットを食べることであれば、あなたの解決策は実行可能な解決策を達成するにはあまりにも貪欲です。ヒューリスティックを再設計する方法は次のとおりです。 -

目的：すべてのペレットを最小経路長で食べます。

ヒューリスティック概算：

1>独立してペレットに現在の位置からのすべての最短経路を計算する*を使用。

2。>コスト関数：（未知のペレットすべての電流からの最短経路の合計）* 2 +開始状態からの総距離。

コスト関数は上限です。

注：各状態で未投与ペレットへの最短経路を計算するための効率的な方法があります。いくつかの研究が必要だろう。