最大非支配集算法

Question

寻找下一个问题的算法： 给定二维平面上的n个点的集合S，如果x1 > x2且y1 > y2，则点（x1，y1）支配另一个点（x2，y2）。找到最大的点集M，使得M是S的子集，并且M中没有任何点被S中的另一个点支配。

- user1256960

---

一个不错的小问题，谢谢。 - n. m.

user1256960，我通过添加集合名称S和M来编辑了问题。如果您的意思是另一个点在S中而不是M中，请将最后一句话更改为“S中的任何点”。（原始问题在其他点是在S还是M中方面存在歧义。） - James Waldby - jwpat7

这基本上是一个带约束的图上最大独立集问题。一般问题是NP完全问题，因此你无法得到比O(2^n)更差的复杂度。 - John Dvorak

Answer 1

按x坐标递增的顺序对所有点进行排序。如果两个点具有相同的x坐标，则按y坐标递减排序。现在，可以证明，仅当在我们排序的序列中它们的y坐标非递增时，一组点是非支配的，这意味着每个y坐标在子序列中小于或等于前一个。

因此，算法如下：

1. 按上述方法对点进行排序。时间：O(n*logn)。 2. 找到最长的非递增子序列的y坐标。时间：O(n*logn)。这可以通过调整查找最长递增子序列的算法来完成。

这将在O(n*logn)中给出最大可能的集合。

- interjay

---

我认为#2应该要求“最长非递增子序列”，是这样吗？ - John Dvorak

实际问题要求M中的任何点都不被S中的另一个点所支配。 - user1256960

@user1256960 嗯，如果你昨天说了这个就好了。你确定吗？这使问题变得非常简单，也不那么有趣：你只需要返回非支配点的集合。 - interjay

Answer 2

有一种分治算法可以在O(n*logn)时间内完成此操作。

让我们根据它们的x坐标将点分成两半，每个部分大小为n/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是非主导点的数量，需要更深入地了解问题，这是你可以努力拓展的领域。

- Gopick

Answer 3

#include <bits/stdc++.h>
using namespace std;

bool comp(pair<int,int> a,pair<int,int> b) {
    if(a.first<b.first)
        return true;
    else if(a.first==b.first) {
        if(a.second<b.second)
            return true;
        else
            return false;
    }
    return false;
}

int main() {
    int n,x,y;
    cin>>n;
    vector <pair<int,int>> points;
    vector <int> brr;
    for( int i=1;i<=n;i++ ) {
        cin>>x>>y;
        points.push_back({x,y});
    }
    if(n==1) {
        cout<<"1\n";
        return 0;
    }
    sort(points.begin(),points.end(),comp);
    priority_queue <int> point_y;
    for( int i=n-1;i>=0;i-- ) {
        while(!point_y.empty()) {
            if(point_y.top()>points[i].second)
                point_y.pop();
        }
        if(i>=1&&points[i].first==points[i-1].first) {
            brr.push_back(points[i].second);
        }
        else {
            point_y.push(points[i].second);
            for(int it : brr )
                point_y.push(it);
            brr.clear();
        }
    }
    cout<<point_y.size()<<endl;
}

这可能会对你有所帮助... 我正在做的是，首先对点进行排序(x1<x2) || (x1==x2&&y1<y2) 然后从末尾开始迭代，弹出优先级队列中y大于该点的值

- raashid