如何找到O(nh)和O(nlog(h))复杂度的帕累托最优点? [英] How do I find the Pareto-optimal points in O(nh) and O(nlog(h)) complexity?

问题描述

有人可以建议一种算法来找到帕累托最优点(形成阶梯)，就像在 O(n * h)和 O(n * log(h))时间复杂度，其中 h 是帕累托最优点的数量吗?

Can anybody suggest an algorithm to find Pareto-optimal points (to form a staircase) just as given in diagram in O(n*h) and O(n*log(h)) time complexity, where h is the number of Pareto-optimal points?

我使用礼物包装算法来解决这个问题(在 O(n * h)中)，但是它只能找到楼梯的凸包类型，而错过那些形成凹角的点.

I used gift wrapping algorithm to solve this (in O(n*h)), but it only finds convex hulls type of staircase and misses those points who form concave angles.

推荐答案

将建议放在一个地方.

想法是使用分而治之的策略.如果我们可以找到在O(n)中将其余pareto点拆分为一半的pareto点P，则可以在O(n log(h))中完成.可以通过在P的右侧，P的左侧和上方，P的左侧和下方三个部分中拆分点来检查.第三组没有pareto点.并在其他两组点上递归执行相同的过程.设置三个部分按比例分割点: a，b，1-a-b .这种复杂性是:

Idea is to use divide and conquer strategy. If we can find pareto point P which splits rest of pareto points in half's in O(n) than it can be done in O(n log(h)). That can be checked by splitting points in three parts right of P, left and up of P, left and down of P. Third set doesn't have pareto points. And recursively do same procedure on other two set of points. Set that three parts split points in ratio: a, b, 1 - a - b. With that complexity is:

T(n, h) = T(a*n, h/2) + T(b*n, h/2) + O(n)
       <= T(n, h/2) + O(n)
       <= T(n, h/4) + 2 * O(n)
       <= T(n, h/8) + 3 * O(n)
       <= ...
       <= O(n log(h))

问题是在< = O(n)中找到具有该特征的对等点.一些简单的启发式算法，例如P，其中x> =(min(x)+ max(x))/2，可能会得出很好的平均值.

Problem is finding pareto point with that characteristic in <= O(n). Some simple heuristic like P where x >= (min(x) + max(x)) / 2, probably makes very good average.

我不确定，但是我认为可以使用第k阶统计查找具有该特征的点.类似于在快速排序中找到中位数作为枢纽.

I am not sure, but I think it is possible to use k-th order statistic to find point with that characteristic. Similar to finding median as pivot in quicksort.

这篇关于如何找到O(nh)和O(nlog(h))复杂度的帕累托最优点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！