[解決済み】パックマン：主にどのようなヒューリスティックが使われているのですか？

質問事項

A*、BFS、DFSなどの他に、パックマンでよく使われる良い経路探索アルゴリズム/ヒューリスティックは何ですか？パックマンが見つけるべき果物が1つ以上ある場合、私が挙げたものはうまくいかないと思うのですが。

パックマンができるだけ少ない歩数で迷路をクリアできるような、良い経路探索アルゴリズムが欲しいのです。目安になるものを探してみましたが、今のところ見つかりませんでした。マンハッタン距離のA*はどこでも言及されていますが、取得する果物が1つ(または2つ？あるいは数個まで？)しかない迷路にしか使えません。

ちなみに、シンプルに、幽霊がいない前提で。

初代パックマンの問題からいくつか例を挙げます。 最初 , 第二 と サード

解決方法は？

コメントによると、探しているのは 最短経路 . この問題は、以下のバリエーションです。 ティーエスピー であり、平面グラフの NPハード .

に対する可能なヒューリスティック関数 A* 問題を解決することができるが 許容される [従って、見つかった経路が最適であることは保証されない]。

すべてのフルーツからエージェントまでのマンハッタン距離の総和。

また、エデュケーション可能なヒューリスティックとして、以下のものを使用することもできます。 #fruits - が、時間がかかる。

最適なものを探すとなると、まあ......難しいですね。あなたは <強い 果物のあらゆる組み合わせに挑戦 というように、「移動距離の合計」を確認します。この解答は 果物の個数の階乗 もしそれが20より大きいなら、素朴なブルートフォースでは時間がかかりすぎます。この問題を解決するには 問題をTSPに縮小する そして、指数関数的でもある動的プログラミングによる解決策や、TSPのヒューリスティックな解決策を利用するのです。

また、非許容的なヒューリスティック解を改良して いつでも使えるアルゴリズム :

繰り返し実行 A* ヒューリスティック関数を減少させながら : h(v) = h'(v) / m ここで h' はA*の最後の繰り返しに関するヒューリスティック関数であり m > 1 . これは、ある時点で、あなたのヒューリスティック関数が h が許容され、見つかった解が最適となる。しかし、各反復は前のものよりもずっと長くかかると予想される（指数関数的に長くなる...）。