c++ - 用于存储帕累托最优解的高效结构

Question

我正在尝试解决需要在计算过程中存储帕累托最优解的问题。我将一组帕累托最优解称为 Bag。

到目前为止，我只有两个标准，这允许基于数组的非常有效的解决方案，其中元素根据第一个标准按降序排序，并根据第二个标准按升序排序。这种数组的一个例子是:

[(100, 0), (50, 1), (-10, 3)]

(关于帕累托最优 - wiki)

但是最近我发现我需要添加第三个标准，对于这样的扩展，上述方法似乎并不适用。我试图用谷歌搜索是否有人已经解决了这个问题，但没有找到令人满意的结果。也许我在问谷歌错误的问题。

更准确地说我需要的:能够存储相互非支配的帕累托最优元素的结构。我需要将元素插入到结构中，我需要遍历元素但没有特定的顺序。在我的例子中，通常不会超过 4-5 个元素，但有时会超过 10-20 个。在我的算法中，插入包的次数非常频繁，因此我需要它们尽可能快。

该应用程序是用 C++ 编写的，但它可能并不真正相关。

如有任何帮助，我们将不胜感激。

编辑:我已经有了自己的一些想法 - 将元素排列成某种三角形结构，但我无法将这个想法形式化。

Edit2:请注意，我要求在每次插入后，结构中只保留相互非支配的元素。例如，如果我有一组非支配三元组 {(1,2,3), (3, 1, 1)} 并添加三元组 (3, 3, 3) 我会设置 {(3,3,3)}。

Edit3:为了更清楚地说明元素的支配地位——我们说，在这种特殊情况下，三元组 (a,b,c) 支配 ( e,f,g) 当且仅当 a >= e && b >= f && c >= g 并且至少有一个不等式是严格的 - >。

Answer 1

首先是简单的方法，这样我们就可以看到我们尝试改进和验证的内容，这个答案实际上与问题相关。

// Taken from the question and translated.
// Is the dominance condition.
let x_doms_y x y =
    let (a,b,c) = x
    let (e,f,g) = y
    a >= e && b >= f && c >= g &&
    (a > e || b > f || c > g)

Naive 方法需要 O(n) 次测试，以便过滤掉数据集中的现有元素，这些元素由要添加的新项目控制。下面显示了朴素的 O(n) 解决方案，随后我们尝试对其进行改进。

type Triplet = int * int * int
type TripletSet = Triplet list

module Naive =
    let insert (t : Triplet) (tset : TripletSet) : TripletSet =
        t :: (tset|> List.filter (fun u -> not (x_doms_y t u)))

从一个空列表开始，然后在下一个 yield 之后添加一个三元组:

let foo =
[] |> show
|> Naive.insert (1,2,3) |> show
|> Naive.insert (3,1,1) |> show
|> Naive.insert (3,3,3) |> show

> []
  [(1, 2, 3)]
  [(3, 1, 1); (1, 2, 3)]
  [(3, 3, 3)]

这似乎符合预期。

为了提高速度，在所选数据结构的插入成本旁边，此处不应考虑，但可能相关，我们尝试将优势比较的次数减少到 < n。平均而言，至少。

这个问题可以用几何意义来解释。三胞胎，例如1,2,3 可以看作是从位于 0,0,0 的立方体一端到其对角线角的 vector 。

体积较小的立方体能否支配较大的立方体？答案是不。我们可以在一维等价物上通过类比来证明这一点。如果 x < y，x 不能支配 y 因为要支配，它应该满足 x >= y && X > y。

可以为二维构想类似的等价关系。这对我们的三胞胎也有同样的意义。

现在，我们缩小了搜索范围。现有集合中体积小于新三元组的那些项目可以但不必由新三元组支配。体积大于新三元组的不能被支配。

因此，一种改进的方法是:

• 令 qset 为已排序的四元组序列，已插入。
• 令 vt 为新三元组 t 的体积:(a,b,c)。 vt = a * b * c
• 令 qt = (vt,a,b,c)
• 使用二进制搜索按体积查找 qset 中的索引位置。
• pos 左侧的所有四元组(v < vt)都是过滤的候选对象。
• pos 右边的所有 quadlets 都不能被支配，因为它们更大。
• 所以，现在，我们只需将朴素方法应用于子集 qset[0..pos-1]。如果插入的值关于此关系是随机的，平均而言，我们只需过滤 n/2，其中 n 是 qset 的大小。
• 将qt at pos插入qset并返回qset。