algorithm - 找到帕累托边界的具体分治算法的参考实现

Question

给定任何部分可排序元素的集合，可以将所述集合的最大值作为不小于集合中任何其他元素的所有元素。当这个集合是一组 n 维向量时会发生一种特殊情况（在 Rust 中，我们可以有类似(D1,D2,D3,...,Dn)n 维向量的类型并且Vec<(D1,D2,D3,...,Dn)>可以是 n 维向量集合的类型），其中每个维度Di是完全有序的，偏序定义为(a1,a2,a3,...,an)<=(b1,b2,b3,...,bn)iff (a1<=b1) && (a2<=b2) && (a3<=b3) && ... && (an<=bn)。在这种情况下，最大值在多个领域中是众所周知的，因为如果维度被解释为要优化的目标，它就是帕累托边界，如果维度被解释为表的列，它就是天际线查询的结果。

在Bentley80和其他几篇论文中，描述了一种找到该最大值的有效算法。这是我目前对其外观的理解（所以请阅读原始描述，因为这个描述来自一个实际上并不知道它是如何工作的人！）：

---

参数：向量的集合V:Vec<(D1,D2,D3,...,Dn)> where D1,D2,D3,...,Dn:Ord，按其第一个维度D1和多个n>=3维度排序。

结果：一个集合M恰好具有 的最大值V。

脚步：

1. 如果集合只包含一个向量或者是空的，我们就完成了；M=V. 否则，继续执行步骤 2。
2. 选择 cross 的中值，并将集合分成两半，其中分量小于中值的V所有向量在 中，其他向量在 中。DnDnV1V2
3. 递归计算 和 的最大值，V1分别V2得到M1和M2。
4. 如果，则沿n == 3迭代，从具有最大分量的向量开始，以最小分量结束。对于本次迭代中的每个向量，如果是 in ，则将其放入，如果它是最大的，则记录其分量。否则，在; 如果它的分量不小于对向量观察到的记录，则将其放入。迭代完成后，我们也完成了；结果是。M_1.append(M_2)D1D1vvM2MD2vM1MD2M1M
5. 如果n > 3，则递归计算 的最大值M1.append(M2)，但将其n - 1作为考虑的最大维度，并跟踪哪些向量在 中，哪些向量在M1中M2。

---

不幸的是，我自己无法实现它。所以我问 StackOverflow：有人可以提供一个简单、可理解的算法实现吗？不需要特定的编程语言，实际上伪代码在这种情况下可能是最明确的选择，但我必须要求不要省略细节。在我看来，像 C 或 Rust 这样的系统语言会对此有所帮助。

当然，我自己（在 Rust 中）也尝试过这样做，但有几件事让我感到困惑：

• 一个。您如何Dn有效地将收藏品分成两半？Rust 在其标准库中有一种查找中位数的方法，但它是不稳定的（在排序意义上），我们不能直接使用它，因为我们需要保留D1顺序。无论如何都可以浪费一堆空间/分配来做它（克隆集合，在克隆上调用标准库方法并找到中值，然后迭代原始向量，将Dn分量小于中值的元素推入V1和更大进入V2），但我想知道是否有更好的方法。
• 湾。重复的元素很棘手。在两个地方，特别是：在第 2 步中，如果中位数有很多重复，人们会想知道是否需要特别注意将它们放在哪里（非中位数元素的数量重要吗？），这甚至可以退化为所有元素都等于中位数的情况，这意味着需要一个特殊的步骤来在发生这种情况时简单地跳过该维度。在第 4 步中，可以同时存在许多具有相同分量D1的向量。我认为在这种情况下需要做的是算法必须遍历具有该组件的所有元素，跟踪向量达到的最高记录，然后才决定是否有M1M2D1M2M1向量进行切割。
• C。您可能已经注意到，第 5 步提到了跟踪哪些向量来自M1和哪些来自M2，但没有其他步骤使用此信息。事实证明我也不知道发生了什么。我的意思是，我读过这篇论文，我“明白了”；因为M2向量具有Dn比任何M1向量严格更大的分量，这意味着，在递归调用中，否则我们只考虑n - 1维度，我们还必须跟踪向量的来源，以便每当v2 <= v1和v1被v2视为-n - 1维向量，但v2来自M2和v1来自M1，我们知道这样说v1和v2实际上是无法比拟的。但是我们不直接在算法中比较向量！实际比较（D2向量的分量之间）在步骤 4 中完成，此时我们与其他维度相去甚远，我不知道如何将来自它们的信息整合到步骤中。我最好的猜测是用一个额外的位向量来“增强”每个向量，每个维度一个位，这样在每个降维递归之前，一个通过 and 中的每个向量M1，M2翻转适当的位，但是然后呢？在第 4 步的迭代部分，我认为您必须跟踪整个D_2记录向量？在这一点上，我基本上停止了自己的尝试。

标签： algorithmimplementationdivide-and-conquerpareto-optimality