3

2000 x 2000 の 2D bool 配列を考えてみましょう。100,000 個の要素が true に設定され、残りは false に設定されます。

セル (x1,y1) が与えられた場合、最も近いセル (x2,y2) (マンハッタン距離: abs(x1-x2) + abs(y1-y2)) で false を見つける必要があります。

それを行う1つの方法は次のとおりです。

for (int dist = 0; true; dist++)
    for ((x2,y2) in all cells dist away from (x1,y1))
        if (!array[x2,y2])
            return (x2,y2);

最悪の場合、空いているセルを見つける前に 100,000 個のセルを反復処理する必要があります。

この検索をより迅速に実行できるようにするために、2D 配列ではなく使用できるデータ構造はありますか?

4

2 に答える 2

4

データが一定であり、それに多くのクエリがある場合: kd ツリー
を使用して、最近傍を探すことができます。のような要素ごとに挿入します。標準のkdツリーはユークリッド距離を使用していますが、代わりにマンハッタン距離を使用するように変更できると思います..(i,j)arr[i][j] = false

データが 1 つのクエリに使用される場合: データを読み取って任意のデータ構造に挿入するには、
少なくとも ops が必要です。そのため、それを行う意味はありません。提案されたソリューションは、任意のデータ構造の構築のみを凌駕します。Omega(n*m)

于 2012-06-26T08:39:35.517 に答える
2

Region QuadTreeを調べることに興味があるかもしれません。ここでは、イメージにすべて 0 が含まれているため (仮定)、最初はイメージ全体がルートとしてモデル化されます。次に特定のピクセルを設定すると、まず画像を 4 つの象限に分割し、ピクセルが含まれていない 3 つの象限を葉として残します。残りの象限は再び分割されます。これは、4 つのポイント リーフのうち 1 つが設定されるまで到達します。この表現は、検索中に領域全体を除外するのに役立ち、検索時間を O(log n) に最適化できます。

于 2012-06-26T13:04:48.020 に答える