10

x1 ≤ x2 かつ y1 ≤ y2 の場合、座標 (x1,y1)の点が別の点 (x2,y2)を支配しているとします。

ポイントのセット (x1,y1) , ....(xn,yn) があり、優勢なペアの総数を見つけたいと考えています。すべてのポイントを相互に比較することで力ずくでこれを行うことができますが、これには O(n 2 ) の時間がかかります。代わりに、分割統治アプローチを使用して、時間 O(n log n) でこれを解決したいと考えています。

現在、次のアルゴリズムがあります。

  • ポイントの集合を P leftと P rightの 2 つの等しいサブセットに分割する垂直線を描画します。基本的なケースとして、あと 2 点だけあれば、直接比較できます。

  • P leftと P rightの支配的なペアの数を再帰的に数えます

  • いくつかの征服ステップ？

問題は、ここで「征服」のステップがどうあるべきかがわからないことです。P leftから P rightに交差する支配的なペアの数を数えたいのですが、両方の部分のすべてのポイントを比較しないと、O(n 2 ) の時間がかかります。

征服ステップのやり方についてヒントをくれる人はいますか？ これは私の例です

したがって、y 座標の 2 つの半分は、{1,3,4,5,5} と {5,8,9,10,12} です。

分割線を引きます。

4

3 に答える 3

8

両方の半分の点を y 座標の昇順で別々に並べ替えるとします。次に、両方の半分の y 値が最も低い点を見てください。左側の最低点の y 値が右側の最低点よりも低い場合、その点は右側のすべての点によって支配されます。それ以外の場合、右側の最下点は左側の何も支配しません。

どちらの場合でも、2 つの半分のいずれかから 1 つのポイントを削除し、残りの並べ替えられたリストでプロセスを繰り返すことができます。これはポイントごとに O(1) の作業を行うため、合計ポイントが n 個の場合、これは (ソート後に) O(n) の作業を行い、2 つの半分にまたがる優勢なペアの数をカウントします。以前に見たことがある場合、これは配列内の反転をカウントするアルゴリズムに似ています)。

ポイントをソートするのに必要な時間 (O(n log n)) を考慮に入れると、この征服ステップには O(n log n) の時間がかかり、繰り返しが得られます。

T(n) = 2T(n / 2) + O(n log n)

これは、マスター定理に従ってO(n log 2 n) に解決されます。

ただし、これを高速化できます。分割と征服のステップを開始する前に、ポイントを y 座標で事前に並べ替え、O(n log n) の作業を 1 回実行するとします。最も近いポイントのペアの問題に似たトリックを使用して、サイズ n の各サブ問題で O(n) 時間でソートされた各半分のポイントを取得できます (詳細については、このページの下部にある説明を参照してください)。これにより、再発が次のように変更されます

T(n) = 2T(n / 2) + O(n)

必要に応じて、これは O(n log n) に解決されます。

お役に立てれば！

于 2013-10-22T06:56:22.793 に答える
1

このように、サブセットへの分割のためだけに O(n^2) があります...
私のアプローチは異なります

  1. ポイントを X ... O(n.log(n)) でソート
  2. ここで Y を確認します
    • ただし、Xが大きいポイントのみをチェックします（昇順でソートすると、インデックスが大きくなります）
  3. だから今あなたは O(n.log(n)+(nn/2)) を持っています

X と Y のテストを別々に実行し、その後結果を組み合わせると、O(n + 3.n.log(n)) につながるため、さらに高速化することもできます。

  1. ポイントにインデックス属性を追加します
    • ここで、index = 0xYYYYXXXXh は符号なし整数型です
    • YYYY は、Y ソートされた配列内のポイントのインデックスです
    • XXXX は、X ソートされた配列内のポイントのインデックスです
    • 2^16 ポイントを超える場合は、32 ビットより大きいデータ型を使用します。
  2. X の昇順でポイントを並べ替え、インデックス O1(n.log(n)) の XXXX 部分を設定します。
  3. Y の昇順でポイントを並べ替え、インデックス O2(n.log(n)) の YYYY 部分を設定します。
  4. ポイントを昇順でソート O3(n.log(n))
  5. (i < j) の場合、ポイント i は任意のポイント j を支配します。
    • しかし、実際に任意のポイントのすべてのペアを作成する必要がある場合
    • それには O4(nn/2) かかるので、このアプローチは少しの時間を節約します
    • 任意のポイントに単一のペアのみが必要な場合は、単純なループで十分です O4(n-1)
    • この場合、O(n-1+3.n.log(n)) -> ~O(n+3.n.log(n))

それが役に立てば幸いです...もちろん、あなたがその細分化アプローチにこだわっているなら、私はあなたにとってより良い解決策を持っていません.

PS。このため、追加の再帰は必要ありません。3倍のソートと任意のポイントに対して1つのuintのみであるため、メモリ要件はそれほど大きくなく、一般に細分化再帰への再帰呼び出しよりも高速である必要があります

于 2013-10-22T07:23:13.803 に答える
0

このアルゴリズムはO(N*log(N))で実行されます。N は点のリストのサイズであり、O(1)余分なスペースを使用します。

次の手順を実行します。

  1. ポイントのリストを y 座標 (昇順) で並べ替え、同点を x 座標 (昇順) で並べ替えます。
  2. ソートされたリストを逆の順序で調べて、支配的なポイントをカウントします。現在の x 座標 >= これまでに検出された x 座標の最大値の場合、結果をインクリメントし、最大値を更新します。

これは、より大きな y 座標を持つすべてのペアの x 座標が現在の点よりも小さい場合、支配的な点が見つかったことを確実に知っているため、機能します。ソートステップにより、非常に効率的になります。

Python コードは次のとおりです。

def my_cmp(p1, p2):
    delta_y = p1[1] - p2[1]
    if delta_y != 0:
        return delta_y
    return p1[0] - p2[0]

def count_dom_points(points):
    points.sort(cmp = my_cmp)
    maxi = float('-inf')
    count = 0
    for x, y in reversed(points):
        if x >= maxi:
        count += 1
        maxi = x

    return count
于 2016-10-27T10:16:30.703 に答える