最大非支配集合のアルゴリズム

Question

次の問題のアルゴリズム： 2D平面でn点の集合Sを与えると、点（x1、y1）はx1> x2ならば点（x2、y2）を支配し、 y1> y2である。 MがSのサブセットであり、Mのどの点もSの別のポイントによって支配されないような最大の点集合Mを見つける。

Answer 1

x座標を増加することによってすべての点をソートする。 2つの点のx座標が同じ場合は、y座標を小さくして並べ替えます。ここで、y座標がソート順で増加していない場合、つまりy座標がサブシーケンス内の前の座標よりも小さいか等しいことを意味する場合にのみ、サブセットのポイントが非支配的であることがわかります。

だからアルゴリズムは次のようになります。上記のように

1. ポイントをソート。時間：O（n * logn）。
2. y座標の最も長くない非増加部分列を見つける。時間：O（n * logn）。これは、longest increasing subsequenceを見つけるためのアルゴリズムを適合させることによって行うことができる。

これは、O（n * logn）で可能な限り大きなセットを与えます。

Answer 2

O（n * logn）時間にこれを行う分割征服アルゴリズムがあります。

ポイントをx座標に基づいてサイズn/2の2つの半分に分割しましょう。我々は、両方の半分に非支配的な点集合を見つける。右半分にあるすべての非支配的な点が最終的​​なリストに存在することを観察する必要があります。

この見解では、結合ステップを書くことができます。右半分の非支配点のy座標のうち最も低いy座標よりも左下のすべての非支配点を削除しますハーフ。私たちは非支配的な点のセットを持っています。

アルゴリズム：時間

Find the median along x axis - O(n) time 
Find non-dominated points in the right half - T(n/2) 
Find non-dominated points in the right half - T(n/2) 
set of non-dominated points could be on O(n) so, the combine step might have to check O(n) points 

式：

T(n) = 2T(n/2) + O(n) which is O(n*logn) 

あなたは、H、非支配点の数であり、O（N * LOGH）このさらに向上させることができ問題の詳細を把握する必要があり、作業を進める上では優れた拡張方法です。