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

Question

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

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

也有人说，很容易详细说明实现此目的的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)
}

标签： algorithmsortingoptimizationmathematical-optimizationpareto-optimality

Answer 1

这个问题的有效贪心解决方案背后的直觉在于一个点i由点jiffx[i] > x[j] 和 y[i] > y[j]支配，这意味着当点按任一坐标排序时j必须在之前。i因此，如果我们以 x 坐标的递增顺序遍历这些点，那么j支配点的点（如果有的话）i必须在点被遍历之前i被遍历。换句话说，在这个排序中，支配点不可能j出现在支配点之后。i

因此，使用这种遍历顺序，支配问题（即检查一个点是否被其他点支配）归结为检查我们是否已经看到一个具有较低 y 坐标的点，因为遍历顺序已经强制执行 x 坐标条件. 这可以通过检查每个点的 y 坐标到我们目前看到的最低（最小）y 坐标来轻松完成——如果最小 y 坐标小于当前点i的 y 坐标，那么j具有最小 y 坐标占主导地位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
    }
}