問題タブ [poset]

分類アルゴリズムを試しているときに、次のアルゴリズムの問​​題が発生しました。要素は多階層に分類されます。これは、単一のルートを持つ半順序集合であると私は理解しています。集合被覆問題によく似た次の問題を解決する必要があります。

ラテックスで作成した問題の説明をここにアップロードしました。

1と2を満たす近似アルゴリズムを考案するのは非常に簡単です。Gの頂点から開始して「上に移動」するか、ルートから開始して「下に移動」します。ルートから開始し、頂点を繰り返し展開してから、少なくともk個の副格子ができるまで不要な頂点を削除するとします。近似限界は、頂点の子の数に依存します。これは、私のアプリケーションでは問題ありません。

この問題に固有名があるかどうか、または問題のツリーバージョンがあるかどうかを誰かが知っていますか？この問題がNP困難であるかどうかを知りたいと思います。おそらく、誰かがNP困難な問題を減らすためのアイデアを持っているか、問題を解決するための多項式アルゴリズムを持っているかもしれません。あなたが両方を持っているならば、あなたの百万ドルの価格を集めてください。;）

膨大な数の並べ替えアルゴリズムがありますが、それらのほとんどは、任意の 2 つの要素が比較可能であると想定しているため、完全に順序付けられたセットでのみ機能します。ただし、一部の要素が比較できない場合に、ポーズセットをソートするための優れたアルゴリズムはありますか? つまり、poset から引き出された要素のセット S が与えられた場合、x _i ≤ x _{j , i ≤ j となる順序 x 1} , x ₂ , ..., x _nを出力する最良の方法は何でしょうか?

可変数の要素を持つリストがいくつかあります。各リストはソートされていますが、ソートのアルゴリズムは不明です。リストを、すべてのリストを同じ順序で、重複することなく含む 1 つの大きなリストにマージしたいと思います。

入力例:

1. XS、M、L、XL
2. S、M、XXL
3. XXS、XS、S、L

期待される結果：

• XXS、XS、S、M、L、XL、XXL

期待される結果は、次のように、各入力シーケンスの要素を正しい順序で含むマージ結果を取得するために、入力シーケンスを照合することによって取得されます。

あいまいな位置を持つ要素がある場合、関数は通知する必要があります。ここでは、XXL (M、L、または XL の後に残る可能性があります) になり、XL の後にその位置を手動で指定する必要があります (ここでは、並べ替えアルゴリズムを知っていて、役立つ可能性があるため)。元のリストのように、各ペアを順番に 2 つの要素ごとにペアを定義することを考えました。これから、完全なリストを作成できます。

帰納法によって証明します。空でない有限集合のすべての半順序は、少なくとも1つの最小要素を設定します。

どうすればその質問を 解決できますか？

SQLAlchemy に関して、 Partially Ordered Setの数学的特性を持つ構造を実装しています。この構造では、エッジを一度に 1 つずつ追加および削除できる必要があります。

私の現在の最良の設計では、2 つの隣接リストを使用します。1 つは割り当てリスト (ハス ダイアグラムのほぼエッジ) です。これは、ノードのどのペアが順序付きとして明示的に設定されているかを保持する必要があり、もう 1 つの隣接リストは推移的であるためです。これにより、あるノードが別のノードに対して順序付けられているかどうかを効率的にクエリできます。現在、エッジが割り当て隣接リストに追加または削除されるたびに、推移閉包を再計算しています。

次のようになります。

floyd_warshall()同じ名前によるアルゴリズムの実装です。

これは私に2つの問題を引き起こしています。1つ目は、あまり効率的ではないようですが、代わりにどのようなアルゴリズムを使用できるかわかりません。

Node.recompute_ancestry()2 つ目は、割り当てが発生するたびに、割り当てがセッションにフラッシュされ、適切な接続が確立された後にのみ、明示的に呼び出す必要があるという実用性に関するものです。ORM に反映された変更を確認したい場合は、もう一度セッションをフラッシュする必要があります。祖先の再計算操作を orm の観点から表現できれば、はるかに簡単になると思います。

私は、a_1 <a_2 <... <a_n、およびb_1 <b_2<...<b_nの形式のJavaでサイズ2nのxsayと呼ばれる半順序集合をシミュレートしようとしています。

反復を実行してランダムな線形拡大を取得し、各オブジェクトの「サイズ」を比較します。2つの隣接する位置を切り替えることができる場合は、切り替えます。そうでない場合は、新しい順序で終了します。たとえば、x [i]=a_kおよびx[i+ 1] = b_k切り替えますが、x [i]=a_kおよびx[i+ 1] = a_（k + 1）の場合は切り替えません。（本質的に、これはKarzanov Khachiyanチェーンです）。

私は当初、x [] [] = {a_1 []、...、b_1 []、...}、たとえばa_1 = {a、1}の配列の配列を使用することを考えました。ここで、値を比較できます。簡単に切り替えることができます。今、私はこれを行う他の方法を考えようとしています。以前の質問から、これは特に効率的またはエレガントな方法ではないことがわかります。誰か提案はありますか？

私はこれをアルゴリズムファイナルの最後の質問として持っていました（現在完了しています）：

(x,y) 点の集合 P が与えられたとき、M ( P)を P 上の次の半順序付けが与えられた最大点の集合とします。

したがって：

M(P) を時間計算量 O(nh)、O(n log n)、O(n log h) で計算するアルゴリズムを与えてください (n = |P| および h=|M(P)|)。

私の O(nh) アルゴリズム:

私の O(n log n) アルゴリズム:

O(n log h) アルゴリズムとは何ですか?
私の直感では、これは最初のアルゴリズムを修正したものですが、ポイントごとにスキャンする必要のない巧妙なデータ構造 (おそらくバイナリ ツリーの修正) を使用しています。

一般的なポーズセットのようなアルゴリズムはありますか?
これは、与えられた頂点のリストと、与えられた 2 つの頂点間に有向パスがあるかどうかの一定時間のルックアップが与えられた任意の有向ツリーの葉を見つけます。

Java で抽象データ型として部分的に順序付けられたセットを作成しています。数値セットの反復子バージョンと、関係の反復子を作成する必要があります。要素には整数の HashSet を使用し、リレーションにはペアの ArrayList を使用しました (ペアは、基本的に (x, y) のようなパラメーターとして 2 つの int を取るクラスです)。s 用と r 用の 2 つの反復子を作成する必要がありますが、特定の順序に従うR必要があります。 (x, y) と (y, z) が に属しているR場合、r の反復子は (y, z) を返す前に (x, y) を返す必要があります。

セット内の要素 n がペアの最初の要素であるかどうかを最初にチェックして返すヘルパー メソッドを作成しましたが、それが 2 番目の要素であるかどうかを確認できないようです。最初の要素を確認するにはどうすればよいですか返されるかどうか？

これが私のコードです：

このコードの助けやヒントをいただければ幸いです。ありがとう

編集：

さて、返された要素を保持する新しいセットを追加した後、コードを書きました。これが私が書いたものです。

このコードは正しいですか? また、Eclipse は、ループの外側で値を返す必要があることを示すエラーを表示するようですが、すべてのケースで既に内側に戻っているのはなぜですか? 助けに感謝します

PoSet で見つかった一連の数値を反復処理するカスタム イテレータ クラスを作成しました。これが私のコードです。

問題は、数値を返すときは、半順序規則に従う必要があるということです。つまり、1. (x, y) が に属しているR場合、x は y の前に返される必要があります。

ただし、上記のコードはその順序に従っているように見えますが、重複を作成しています。コードを修正して許可しないようにするにはどうすればよいですか?

注: 私のコードでは、S は PoSet 内の数値のセットであり、それは HashSet であり、R は PoSet 内の関係を保持するためのペア (ペア: 2 つの int をパラメーターとして受け取るクラス) の配列リストです。

この問題を解決する方法はありますか? ありがとう

問題は次のとおりです。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 が比較できないことをどのように知ることができますか? それらは明示的ではないかもしれませんが、暗黙的かもしれません。