15

我有一个部分有序的集合，比如说A = [x1, x2, ...]，这意味着对于集合中的每个xiand xj，（确切地说）四种可能性之一是正确的：xi < xj、xi == xj、xi > xj、 或xi并且xj是无法比较的。

我想找到最大的元素（即那些xi没有元素的元素xj）xi < xj。什么是执行此操作的有效算法（最小化比较次数）？我尝试构建 DAG 并进行拓扑排序，但仅构建图形需要 O(n^2) 比较，这太多了。

我在 Python 中执行此操作，但如果您不知道，我可以阅读其他语言或伪代码。

4

4 回答 4

8

无论您做什么，似乎最坏的情况都是 O(n^2)。例如，如果没有可比较的元素，那么您需要将每个元素与每个其他元素进行比较，以确定它们都是最大的。

如果你允许 O(n^2)，因为排序是传递的，你可以只通过一个集合，保持一个迄今为止最大的所有元素的列表；每个新元素都会剔除任何 < 它的最大元素，如果它不是 < 任何最大元素，则将其添加到最大列表中。

于 2014-02-04T18:50:23.930 回答
4

在最坏的情况下，你不能比 O(n^2) 更快。实际上，要检查所有元素对于没有元素可比较的 poset 是否最大，您需要比较每对元素。所以在最坏的情况下它肯定是二次的。

让我澄清一下回答下面的评论：我声称最坏的情况是当 poset 是没有两个元素可比较的琐碎的 poset 时。在这种情况下，所有元素都是最大的。要检查是否确实如此，任何进行比较的算法都必须执行所有 n(n+1)/2 次比较。事实上，如果比较说 a <-> b 没有被执行，那么算法就不能区分平凡的偏序集和唯一关系是 a < b 的偏序集，所以它不能给出正确的答案。所以任何算法在最坏的情况下必须至少是二次的。

于 2014-02-04T18:52:26.783 回答
2

假设您已经查看了所有（n 选择 2）比较，除了一个，在 x i和 x j之间，i != j。在某些情况下，最大的唯一两个候选者正是这两个，x i和 x j。

如果您不比较 x i和 x j，则无法确定它们是否都是最大的，或者是否只有其中一个是最大的。

因此，您必须检查所有可能的 (n 选择 2) (O(n 2 )) 比较。

请注意，这假设您的部分有序集是使用将进行比较的黑框指定的。如果将部分有序集作为一个图表给出，那么您随后可以在 sub-O(n 2 ) 时间内找到最大元素的集合。

于 2014-02-04T19:08:54.227 回答
2

正如其他答案所指出的，最坏情况的复杂度是 O(n^2)。

但是，有一些启发式方法可以在实践中提供很大帮助。例如，如果集合 A 是 Z^2（整数对）的子集，那么我们可以通过以下方式预先消除很多点：

  1. 沿 x 轴排序（对于给定的 x 值，例如 1，找到具有最大 y 值的点，对所有 x 值重复）以获得一组候选最大值，称为 y 最大值。
  2. 类似地得到集合 x 最大值。
  3. 相交以获得最终的候选集 xy 最大值。

这是成本 O(n)。很容易看出，任何极大点都将出现在 xy 极大值中。但是，它可以包含非最大值点。例如，考虑集合 {(1,0), (0,1), (2,2)}。

根据您的情况，这可能是一个足够好的启发式方法。您可以在较小的 xy 最大值上使用穷举算法来跟进这一点。

更一般地说，这个问题被称为“Pareto Frontier”计算问题。这里有很好的参考：

http://www.cs.yorku.ca/~jarek/papers/vldbj06/lessII.pdf

https://en.wikipedia.org/wiki/Pareto_efficiency#Use_in_engineering_and_economics

特别是第一个参考文献中的 BEST 算法非常有用。

于 2018-01-06T10:57:32.393 回答