4
問題的最大因素是： 給定一個序集的子集S找到S.找到一個序集的子集
的最大元素例如，考慮偏序集的HASS圖中http://ndp.jct.ac.il/tutorials/Discrete/node34.html。鑑於它的一個子集，例如：{12,2,8}，最大元素是12和8.
我不知道我是否會精確地描述問題。我認爲這個問題可能涉及到傳遞閉包的一些排序或計算，但我有點困惑。
你能給我一些快速算法的方法嗎？我想保留在O（n^2）
謝謝。
稍作澄清。我的應用程序正在使用RDF圖。如果存在代表<關係的特定邊，則兩個節點具有可比性。如果存在這樣的顯式關係或隱式傳遞關係，那麼兩個節點可能是可比較的。
因此，假設hass圖正好是我的RDF圖。如果我從2開始深入優先搜索，我怎麼知道8和12是不可比的？他們可能並不明確，但可能是隱含的。
如果兩個節點是可比較的wrt。訂貨關係，那麼他們中至少有一個必須有一個「轉讓」訂貨關係的後繼節點，對吧？ – 2012-04-13 14:38:48
是的，這是正確的。但是如果你有路徑a-b-c，a和c是「隱含」可比的。基於此，我懷疑我必須計算子集中每個節點的傳遞閉包，並對可比元素進行「清理」。 – Alex 2012-04-13 15:30:03
假設a-b意味着a
2012-04-13 16:15:05