問題は次のとおりです。poset の部分集合 S が与えられた場合、S の最大要素を見つけます。
たとえば、http://ndp.jct.ac.il/tutorials/Discrete/node34.htmlのポーズセットのハス ダイアグラムを考えてみましょう。そのサブセット ex: {12, 2, 8} を考えると、最大要素は 12 と 8 です。
問題を正確に説明しているかどうかはわかりません。問題には、推移閉包のソートまたは計算が含まれている可能性があると思いますが、少し混乱しています。
高速アルゴリズムのアプローチを教えてください。O（n ^ 2）に保管したい
ありがとう。
少し明確にします。私のアプリケーションは RDF グラフを使用しています。< 関係を表す特定のエッジが存在する場合、2 つのノードは比較可能です。そのような明示的な関係または暗黙の推移的な関係がある場合、2 つのノードは比較可能です。
したがって、ハス図がまさに私の RDF グラフであると仮定します。2 から始めて深さ優先検索を行った場合、8 と 12 が比較できないことをどのように知ることができますか? それらは明示的ではないかもしれませんが、暗黙的かもしれません。