问题查找部分有序集的最大元素的有效算法

比方说，我有一个部分订购的套装 A = [x1, x2, ...]，意味着每个人 xi 和 xj 在集合中，（确切地说）四种可能性中的一种是真的： xi < xj， xi == xj， xi > xj，要么 xi 和 xj 是无与伦比的。

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

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

7395

2018-02-04 18:38

起源

成为一个部分有序集不应该xi> xj被禁止？这个想法是，如果它们具有可比性，那么任何两个元素都是有序的。 - Russell Zahniser

@Vallentin阅读了这个问题。我尝试构建图形并进行拓扑排序。 - asmeurer

@RussellZahniser我不确定我理解你的评论，但当然 x < y 被允许。否则你根本就没有订单，只是一组无法比较的元素。 - asmeurer

我知道你的poset是作为元素的列表给出的，比较函数返回说-1,0,1或None。对？ - hivert

我怀疑，但还不能正式证明，O（n ^ 2）的信息理论下界因为我认为总共有2 ^（n ^ 2）个可能的偏序，每个比较只能让你消除大约50％的人一次。这与排序下限证明有关：由于元素有大约2 ^（n log n）个可能的排序，因此需要n log n比较进行排序。 - templatetypedef

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

如果你允许O（n ^ 2），因为排序是可传递的，你可以只通过集合进行一次传递，保留到目前为止最大的所有元素的列表;如果不是<任何最大元素，则每个新元素都会清除任何<it的最大元素并将其添加到最大列表中。

2018-02-04 18:50

也许这个算法实际上很好，而我只是在用DAG思考问题。我希望最小元素很少（99％的时候，应该只有一个）。事实上，如果最大元素集太大，我必须开始考虑我可以放在集合上的新排序，使其再次变小。 - asmeurer

算法的效率要比最坏的情况复杂度要多得多。例如，比较排序完全有序集的算法，bubblesort和quicksort都有O（n ^ 2）最坏的情况下复杂。但是，quicksort有更好的效果平均复杂。在此基础上，您是否确信您的算法是有效的？ - Stewart

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

2018-02-04 18:52

假设您已经查看了除x之外的所有（n选择2）比较_一世和x_Ĵ，我！= j。在某些情况下，只有两个最大候选者才是这两个，x_一世和x_Ĵ。

如果你不比较x_一世和x_Ĵ，你无法明确地说它们是否都是最大的，或者只是其中之一。

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

请注意，这假设您的部分有序集使用黑框进行指定，以进行比较。如果部分有序集以图表的形式给出，您可以随后在子O（n）中找到最大元素集²）时间。

2018-02-04 19:08

正如其他答案所指出的，最坏情况的复杂性是O（n ^ 2）。

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

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

根据您的情况，这可能是一个足够好的启发式。你可以在较小的集合xy-maximals上使用详尽的算法来跟进。

更一般地说，这个问题被称为“帕累托前沿”计算问题。以下是很好的参考：

特别地，来自第一参考的BEST算法非常有用。

2018-01-06 10:57

问题 查找部分有序集的最大元素的有效算法