大きな迷路ですべてのドットを食べる短いパス (最短ではなく、適切なパス) を見つけるという PACMAN 問題の解決策を見つけようとしています。多くの人が TSP、Dijsktra、BFS、A* について話しているのを見てきました。開始した場所に戻る必要がなく、必要に応じてノードを繰り返すことができるため、これは TSP ではないと思います。そして、最短経路を探しているわけではないので、Dijsktra、BFS、および A* が役立つとは思いません。
誰か私にこれについてのヒントを教えてもらえますか? これはどのような問題ですか？これは一種の TSP ですか？効率的な方法でこの問題にアプローチするアルゴリズムはどのようなものでしょうか? 実装に関するヒントをいただければ幸いです。
大迷路の最短経路を 30 秒以内で見つけるコンテストをやろうとしていると思いますか?
私は実際に昨年、楽しみのためにこれを行いました (私の大学のクラスはコンテストを行いませんでした)。数週間の調査の結果、30 秒以内に迷路の正確な解を得ることができました。
私が使用したヒューリスティックは、実際には正確なヒューリスティックでした。グラフ分解と動的プログラミングに基づくはるかに効率的なアルゴリズムを使用して最小パス長を見つけるための一連のコードを作成し、その結果を「ヒューリスティック」値として A* にフィードバックしました。
重要なことは、グラフが非常に大きい (273 ノード) 一方で、カービング幅が小さい (5) ことです。これは、固定パラメーターの扱いやすいアルゴリズムを使用して効率的に解決できることを意味します。
うまくいけば、それが正しい軌道に乗るのに十分なキーワードです.