2

私はこの問題を抱えています：長方形のセット{R1、R2 ... Rn}と新しい長方形Rqが与えられた場合、Rqを配置する場所を見つけて、交差するようにします（面積は関係ありません）内の長方形の最大数セット。複雑すぎるデータ構造を含まない単純な解決策を探していますが、有効な回答は非常に高く評価されます。

4

1 に答える 1

0

これはO(n^2)or O(n (log n + m))(平均的なケースのみ) 複雑性アルゴリズムです (mは交差する長方形の最大数です)。後述の方法を参照してください。O(n log n)

n一つ目は、解決策を探す場所があると考えることです。つまり、各四角形について、交差する最も右の四角形がRiの場合が解の候補です。RiRq

左から右にスキャンします。最小 x 座標の順に四角形をバッファー コンテナーに追加し、(最大 x 座標に基づいて) 優先キューにも追加します。各四角形を追加するときに、(優先度キューに基づいて) どの四角形を削除する必要があるかを確認して、Rq今のところ y 軸を無視した場合に、バッファー内の四角形の範囲が四角形と交差できるようにします。

各長方形をバッファーに追加する前に、交差Riする必要がある場合にバッファー内で交差できる長方形の数を考慮することができます(最も右側の と交差する長方形です)。これは線形時間で実行できます。RqRiRiRq

したがって、全体的な複雑さはO(n^2)です。

アルゴリズムの実行時間は、バッファーに格納されている任意の四角形ノードに間隔ツリーを使用することで改善できます。ウィキペディアには、これとその実装方法に関する十分な情報が記載されているため、ここではどのように機能するかについて説明しません。これにより、平均的な複雑さが に改善されますO(n (log n + m))。ここmで、 は交差する長方形の最大数です (n最悪の場合と同じくらい大きくなる可能性があります)。これは、インターバル ツリーのクエリのアルゴリズムの複雑さ (クエリごとのO(log n + m)時間) によるものです。返される結果の数 (インターバル ツリーの場合) については、答えが のオーダーでなくても最大 になる可能性があるO(n^2)ため、最悪のケースは依然としてです。mO(n)n.

ここではO(n log n)時間の経過に伴う方法に従いますが、非常に複雑です。

四角形を並べ替えられた配列、自己均衡二分探索木 (最小 y のみに基づく)、または間隔ツリーとして格納する代わりに、四角形をカスタム データ構造に格納することもできます。

(最大 y に基づく) 自己平衡二分探索木を考えてみましょう。これにいくつかのメタデータを追加できます。特に、バッファ内で交差する四角形を最大化しようとし、バッファが左から右にスキャンするにつれて最大値がどのように変化するかを探し続けるため、バッファ内の各四角形が一番下にある場合、交差する四角形の数を考慮することができます。矩形。

四角形の数を格納できれば、より高速にクエリできる可能性があります。

解決策は、更新コストを削減するために、別の方法で保存することです。二分探索木には多数のエッジがあります。そのノードが交差する一番下の長方形である場合、各ノードが交差できる長方形の数を知っている必要があるとします。代わりに、各エッジの両側のノードが交差する長方形の数の変化を保存できます (これを と呼びますdiff)。たとえば、次のツリーの場合 (長方形の最小と最大の y を使用):

     (3,4)
      / \
   (2,3) (5,6)

のRq高さが 2 で、(2,3)が一番下の場合、合計で 2 つの長方形と交差できます。 の場合(3,4)は 2 、(5,6)の場合は 1 です。

したがって、エッジdiffは 0 と -1 になり、子から親への答えの変化を表します。

各ノードがそのサブツリーにサブパスの最大合計も格納している場合 ( this と呼びます)、重みを使用して最大数をすばやく見つけることができますmaxdiff。葉の場合は 0 ですが(3,4)、 の場合は 0 と -1 の最大値が 0 であるため、ルート ノードのサブパスのエッジの最大合計として 0 を格納できます。

したがって、最適な答えはルート ノードの答えよりも 0 多いことがわかります。ルート ノードの答えを見つけることができますが、より多くのメタデータを保持します。

ただし、このすべてのメタデータは、log n時間内にクエリおよび更新できます。これは、四角形を追加するときに、それを自己平衡二分探索木に追加するのに時間がかかるためです。回転log nまで行う必要がある場合があります。log nローテーションを行う場合maxdiff、影響を受けるノードだけでなく、エッジのウェイトを更新する必要がある場合がありますが、これはO(1)ローテーションごとです。

さらにdiff、エッジの余分な長方形の効果を更新する必要があります。ただし、ほとんどのO(log n)エッジを更新する必要があります。具体的には、新しい四角形の最小 y と最大 y でツリーを検索すると、更新が必要なすべてのエッジが見つかります (ただし、通過するエッジを更新する必要があるかどうかは関係ありません)。左または右のどちらの子を取得したかによって異なります - 正確なルールを決定するには、ここで慎重な作業が必要です)。

長方形の削除はその逆なので、時間がかかりO(log n)ます。

このようにして、時間内にバッファを更新し、O(log n)時間内にクエリを実行してO(log n)、全体的なアルゴリズムの複雑さをO(n log n).

注:バッファー内で交差する最大の四角形を見つけるには、 を使用しますmaxdiff。これは、最適とルート ノードの答えの差です。実際の答えを見つけるには、二分探索木で最も順序の低い四角形の答えとルート ノードの違いを見つける必要があります。O(log n)これは、最も左側のパスをたどり、diffエッジで合計することで、時間内に簡単に実行できます。最後に、最も順序の低い四角形で答えを見つけます。これは、最小の y で並べられた 2 番目の自己平衡二分探索木を格納することによって行われます。これを使用して、最大 y で並べ替えたときに一番下の四角形が最も順序の低い四角形である場合、交差する四角形の数を見つけることができます。

この余分な BST の更新とクエリにもO(log n)時間がかかるため、この余分な作業によって全体的な複雑さが変わることはありません。

于 2012-09-18T08:59:20.767 に答える