1

サイズ N*N の正方形グリッドで BFS を実行したいと考えています。開始ノードは 1 つです。上下左右にしか動かない（斜めには動かない）。グリッドに障害物がある可能性があります。

もちろん、アクセスする必要があるノードを格納するためにキューを使用したいと考えています。サイズ S (固定サイズ) の円形配列として実装されます。アレイの最小サイズは? 最悪の場合でもオーバーフローさせたくありません。

同様の問題は次のようになります: グリッド内のノードが与えられた場合、開始ノードから正確に K の距離にあるノードの最大数はいくつですか (任意の 0 < K < 2*N の場合)?

この問題に対する正確な答えを見つけるのは難しいと思うので、適切な概算で十分です。

この例を参照してください（一番右の写真）：

ここに画像の説明を入力

これはグリッドではありませんが、同じパターンでグリッドを作成できます (白は障害物を表し、黒のフラクタルは歩行可能なノードです)。中央のノードからまったく同じ距離に多くのノードがあることがわかり ます (実際、この数はパスが 2 つに分割されるたびに 2 倍になります)。したがって、この数値がどれくらい大きくなるか、また同じ状況に陥る他の構成があるかどうかを知りたいです。

非常に明確にするために、私の質問は次のとおりです。この数値は 2*N よりも大きくなることができますか? ここで、N は N*N 正方形グリッドのサイズです。

4

3 に答える 3

0

あなたの問題を正しく理解していれば、開始ノードからノードまでの最大距離は、2*N障害物の存在により> になる可能性があります。

. . . * . . .
. * . * . * .
. * . * . * .
. * . * . * .
. * . . . * .
. . * * * . .
. . A * B . .

正しく数えると、A から B までの距離は 30 で、これは 2*7 よりもはるかに長いです。

障害物がなければ、フリンジの最大サイズを簡単に計算できます。これは、エッジの単純なひし形K(またはグリッドに重なる部分) であり、結果として最大サイズになり2*Nます。

上記の例が示すように、障害物によって、2 つのノード間の最短経路の長さが長くなる可能性があります。可能な最大フリンジサイズを増やすことはできますか? 彼らがそうする例をすぐに思いつくことはできませんし、そうではないのではないかと思いますが、簡単な証明も思いつきません。

于 2012-11-18T23:58:18.040 に答える
0

キューの最大サイズを知りたいので、距離 K にあるセルの数を知りたいのではないでしょうか?

もしそうなら、代わりにリストに基づいた循環バッファを使用しないでください (または、配列を使用して、バッファがいっぱいになったら自分でより大きなものを再割り当てしてください)。

これにより問題が完全にスキップされ、リストのサイズ変更動作は問題になりません。ほとんどの実装では、スペースが不足した場合に基になる配列のサイズが 2 倍になるため、とにかく O(log n) を超える再割り当てを取得しないでください。

于 2012-11-18T20:12:51.783 に答える
0

はい、この数字は大きくなる可能性があると思います。提供された 3 番目の画像を使用すると、非常に簡単に視覚化できるはずです。

その図の左上の 4 分の 1 から始めるとします。これは、N をその左上の 4 分の 1 のサイズとして定義し、E を中央のセルまでの距離がすべて同じ端点の数として定義します。

ここで、グリッドを完全な図に拡張したいとします。これは、Nnew が 2N になったことを意味します (つまり、長さが 2 倍になり、幅も 2 倍になります)。ただし、図からわかるように、エンドポイント E の数は 4 倍になりました (つまり、Enew = 4N)。

つまり、N が増加するにつれて、エンドポイントの数は N よりもはるかに速く増加するため、N が十分に大きい場合、エンドポイントの数は 2*N を超えることになります。

于 2012-11-20T13:24:45.290 に答える