找出最大的不及組，以最小的比較

的不及集可以有成員A B和C，其中A > B > C但C > A。這樣的一套可能是由一個人的喜好排序的照片。找出最大的不及組，以最小的比較

我可以比較輕鬆地查找算法找到的最大一個傳遞集合以最小的工作，甚至進行排序不及物動詞集，但它是很難看到如何將兩者結合起來。

是否有此問題的已知的解決方案？

2013-05-08 bukzor

沒關係算法;如何確定最大值？特別是，您發佈的示例集的最大值是多少？在'A'，'B'和'C'中看起來完全是圓形的。 – 2013-05-08 22:05:08

您可能有興趣閱讀有關部分有序集合和Pareto Optimum。或者你可以提供更多的細節，你想解決排序。如果你有多個數值標準，那麼多維優化將有助於（除去主導元素等） – flaschenpost 2013-05-08 22:08:05

有不能在不及物動詞設定一個最高，其實在剛纔您提供的例子，沒有上限可言... – alfasin 2013-05-08 22:16:29

你有什麼基本上是一個前序，這可以通過一個有向圖來表示。由於它不是酰基類，所以沒有獨特的種類。但是，您可以執行深度優先遍歷，這將爲您提供圖的某些子森林的拓撲排序。

您還可以找到通過各種算法的強連接組件（的Tarjan的是我的最愛）。

2013-05-08 22:08:18 Antimony

你假設整個圖都可用。查找圖的每個邊有一個成本應該儘量減少。另外，爲了確定拓撲排序，並非必須知道圖中的每條邊。鑑於這些限制，我認爲這是一個不同的問題。 – bukzor 2013-05-09 22:41:54

回答