algorithm - 最大非優越集合のアルゴリズム

Question

次の問題のアルゴリズムを見つける: 2D 平面内の n 個の点の集合 S が与えられた場合、x1 > x2 および y1 > y2 の場合、点 (x1, y1) は別の点 (x2, y2) を支配します。M が S のサブセットであり、M のどの点も S の別の点によって支配されないように、点 M の最大のセットを見つけます。

Answer 1

x 座標を増やしてすべての点を並べ替えます。2 つの点の x 座標が同じ場合は、y 座標の降順で並べ替えます。ここで、ソートされたシーケンスで y 座標が増加していない場合、つまり各 y 座標がサブシーケンスの前の座標より小さいか等しい場合にのみ、ポイントのサブセットが非優勢であることを示すことができます。

したがって、アルゴリズムは次のようになります。

1. 上記のようにポイントを並べ替えます。時間: O(n*logn)。
2. y 座標の最長の非増加サブシーケンスを見つけます。時間: O(n*logn)。これは、最長増加サブシーケンスを見つけるためのアルゴリズムを適応させることによって行うことができます。

これにより、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 left 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)

これをさらに O(n*logH) に改善することができます。ここで、H は非支配点の数です。これには、問題に対するより多くの洞察が必要であり、作業するのに適した拡張機能です。