相关疑难解决方法(0)

我在3D空间中有一组点,我需要从中找到Pareto前沿.执行速度在这里非常重要,并且当我添加测试点时,时间会非常快.

点集看起来像这样:

[[0.3296170319979843, 0.0, 0.44472108843537406], [0.3296170319979843,0.0, 0.44472108843537406], [0.32920760896951373, 0.0, 0.4440408163265306], [0.32920760896951373, 0.0, 0.4440408163265306], [0.33815192743764166, 0.0, 0.44356462585034007]]

现在,我正在使用这个算法:

def dominates(row, candidateRow):
    return sum([row[x] >= candidateRow[x] for x in range(len(row))]) == len(row) 

def simple_cull(inputPoints, dominates):
    paretoPoints = set()
    candidateRowNr = 0
    dominatedPoints = set()
    while True:
        candidateRow = inputPoints[candidateRowNr]
        inputPoints.remove(candidateRow)
        rowNr = 0
        nonDominated = True
        while len(inputPoints) != 0 and rowNr < len(inputPoints):
            row = inputPoints[rowNr]
            if dominates(candidateRow, row):
                # If it is worse on all features remove the row from …

我有一个偏序集,说A = [x1, x2, ...],这意味着每一个xi和xj集合中的,(恰好)的四种可能性之一为真:xi < xj,xi == xj,xi > xj,或xi与xj所无法比拟的.

我想找到的最大元素(即,这些元素xi是针对那些还没有元素xj用xi < xj).什么是有效的算法(最小化比较次数)？我尝试构建DAG并进行拓扑排序,但只是构建图形需要进行O(n ^ 2)次比较,这太多了.

我在Python中这样做,但如果你不知道它我可以读其他语言,或伪代码.