帕累托边界（集合）：算法的顺序

Question

我必须完成一项挑战，该挑战涉及制定计算帕累托（集合）边界的算法。声明基本上是：

给定正方形[0,1] x [0,1]中n个点的集合S，做一个算法来确定S包含的子集P，由S的非支配点组成。

也有人说，很容易详细说明实现此目的的 n*n 阶点比较的算法。好吧，我通过到处研究想出了一个算法。挑战仍然是实现 n*log(n) 阶的算法。我如何获得这些算法的顺序？

提前致谢！

#data
set.seed(103)
x = runif(200)
y = runif(200)

#algorithm
pareto = 1:length(x)
for(i in 1:length(x)){
    cond1 = y[i]!=min(y[which(x==x[i])])
    cond2 = x[i]!=min(x[which(y==y[i])])
    for(k in 1:length(x)){
        if((x[i]>x[k]  &  y[i]>y[k]) | (x[i]==x[k] & cond1) | (y[i]==y[k] & cond2)){
            pareto[i] = NA
            break
        }
    }
}
xPareto = x[pareto[!is.na(pareto)]]
yPareto = y[pareto[!is.na(pareto)]]

#graphic:
plot(x, y)
points(xPareto, yPareto, col=2, pch=16)
dat = data.frame(x=xPareto, y=yPareto)
dat = dat[order(dat$x),]
for(i in 1:(nrow(dat)-1)){
    segments(dat$x[i], dat$y[i], dat$x[i+1], dat$y[i+1], col=2, lty=2)
}

Answer 1

这个问题的有效贪婪解决方案背后的直觉在于点 i 被点 j 支配当且仅当 x[i] > x[j] 和 y[i] > y[j]，这意味着当点按任一坐标排序时，j 必须在 i 之前。因此，如果我们按 x 坐标的递增顺序遍历这些点，那么控制点 i 的点 j（如果有的话）必须在 [=40= 之前被遍历]点i被遍历。也就是说，在这个排序中，支配点j不可能在支配点i之后。

因此，对于这种遍历顺序，支配问题（即检查一个点是否被其他点支配）归结为检查我们是否已经看到具有较低 y 坐标的点，因为遍历顺序已经强制执行x 坐标条件。这可以通过将每个点的 y 坐标检查到我们目前看到的最低（最小）y 坐标来轻松完成——如果最小 y 坐标小于当前点 i 的 y 坐标那么具有最小 y 坐标的点 j 支配 i 为 x[j] < x[i] 因为 j 在 i.
之前被看到
按 x 坐标排序需要 O(n log n) 时间，检查每个点（同时保持部分最小 y 坐标）需要 O(n) 时间，使得整个算法需要 O(n log n)时间。

o = order(x) minY = Inf pareto = 1:n for(j in 1:n){ i = o[j] if (y[i] <= minY) { # Part of pareto boundary minY = y[i] } else { # Dominated by some point in pareto boundary pareto[i] = NA } }

帕累托边界（集合）：算法的顺序

Pareto boundary (set): Order of an algorithm

algorithm

sorting

optimization

mathematical-optimization

pareto-optimality