ブロックの形で障害物がある nxn グリッドがあります。ランダムなポイントから開始して、このグリッドのどこかにフラグを見つける必要があります。左右に曲がったり、前後に移動したりできます。
グリッドの各ポイントで、自分の 4 つのブロック (上、下、左、右) に関する情報を取得します。BFS は良い解決策のようです。しかし、より高速またはより優れた探索アルゴリズムがあるかどうか疑問に思いました。
どんなアイデアでも大歓迎です。
2 に答える
0
これは、グリッドでの通常の探索の問題のようです。BFSを使用する場合、距離<=開始とフラグの間の距離を持つすべてのポイントを検索します。
ただし、いくつかの最適化を使用することをお勧めします。
旗の座標がわかっている場合は、A *を使用できます（質問からは不明です）。
旗の座標がない場合は、ブロックから取得した情報を利用してみてください。正方形のグリッド上で、BFSは円形の検索フロントを作成します。これは、開始点の周りの円形の領域内のポイントに関するすべての情報を取得することを意味します。これは、その地域のすべてのポイントを評価することを意味します。グラフ上でより多くの情報を提供するポイントの評価に優先順位を付けることで、探索を最大化することができます=多くの未知の隣接点があるポイント。
これにより、検索がリダイレクトされ、できるだけ早く新しいポイントが評価されます。旗を見つけたら、距離に上限があり、境界を改善する可能性のあるグラフの未知の部分を探索できます。検索が行き過ぎないように、優先度関数で開始からの距離を考慮することもできます。優先機能のバランスは、グリッドと障害物の量によって異なります。
于 2013-03-11T11:07:11.887 に答える
0
BFS は確かに必要なアルゴリズムです。追加の利点として、フラグに交差するセルに関して最短パスを見つけることができます。また、グラフ全体を「従来の方法」で保存する必要がないことに注意してください。この場合、グリッドはグラフ自体の十分な表現です。私の生徒の多くはそれを理解できていません。
于 2013-03-10T16:35:35.420 に答える