算法的最大非支配集 [英] Algorithm for maximum non-dominated set

问题描述

查找算法下一个问题： 给定的n个点组S在2D平面，一个点（X1，Y1）占主导地位的另一点（X2，Y2）如果X1> X2和Y1> Y2。找到的点的最大集合M，M为S的子集，并没有点M的由另一点S的支配。

FInd an algorithm for the next problem : Given set S of n points in the 2D plane, a point (x1, y1) dominates another point (x2, y2) if x1 > x2 and y1 > y2. Find the largest set of points M such that M is a subset of S and no point of M is dominated by another point of S.

推荐答案

按x增加坐标排序的所有问题。如果两个点具有相同的x坐标，通过降低y坐标对它们进行排序。现在，可以证明，点的子集是非支配当且仅当其y坐标是不增加我们的排序序列中，这意味着每个y坐标小于或等于previous一个在子序列

Sort all points by increasing x coordinates. If two points have the same x coordinate, sort them by decreasing y coordinates. Now, it can be shown that a subset of points is non-dominated if and only if their y coordinates are non-increasing in our sorted sequence, meaning each y coordinate is less than or equal to the previous one in the subsequence.

所以，算法是：

1. 排序点如上所述。时间：O（N * LOGN）
2. 找到y坐标的最长的非增序列。时间：O（N * LOGN）。这可以通过调整算法寻找最长递增子来完成。

1. Sort the points as described above. Time: O(n*logn).
2. Find the longest non-increasing subsequence of y coordinates. Time: O(n*logn). This can be done by adapting the algorithm for finding the longest increasing subsequence.

这使在澳最大可能设定为（n * LOGN）。

This gives the largest possible set in O(n*logn).

这篇关于算法的最大非支配集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！