問題タブ [disjoint-sets]

リンクリストとしての素集合に関する情報を誰かに教えてもらえますか？これに関するコードが見つかりません。言語C++

STL がset_differenceであることは知っていますが、 2setが互いに素であるかどうかを知る必要があります。コードのプロファイリングを行ったところ、アプリの速度がかなり低下しています。2 つのセットがばらばらであるかどうかを確認する簡単な方法はありますか?それとも、自分のコードをロールするだけでよいのでしょうか?

編集：私も試しset_intersectionましたが、同じ時間がかかりました...

素集合データ構造を調べたところ、「ユニオン検索データ構造」とも呼ばれ、ユニオンと検索がこのデータ構造の2つの主要な操作であることがわかりました。互いに素な集合に対して結合を実行できます。同様に、検索操作を実行できます。unionとfindを除いて、互いに素な集合に対して実行できる他の操作を知りたいです。

私たちの先生は和集合と検索操作だけを説明したため、C++ で素集合 ADT を実装する際に問題があります。union と find の概念を完全に理解していますが、それらを実装する方法についてはまだ混乱しています。

誰かが私に実装のアイデアを教えてください。また、このデータ構造のインターフェースがどのように見えるべきかを説明してもらえますか?

ウィキペディアの素集合フォレストの和集合/検索アルゴリズムの内訳は次のとおりです。

• ばらばらなばらばらの森... ( O(n))
  • ... ランクごとに結合 ... (現在は に改善O(log(n))
    • ...パス圧縮あり（現在O(a(n))、効果的に に改善されていますO(1)）

ランクによる結合を実装するには、各ノードがrank比較のためにフィールドを保持する必要があります。私の質問は、ランクによる結合はこの追加スペースの価値があるかということです? ランクによる結合をスキップして、代わりにパス圧縮を行うとどうなりますか? それは十分ですか？現在の償却複雑度は?

O(log(n)パス圧縮 (償却された複雑さ) のないランクによる結合は、ほとんどの実用的なアプリケーションに十分であることを意味するコメントが作成されます。正解です。私が求めているのは逆です: ランクによるユニオンをスキップして、代わりにパス圧縮のみを行うとどうなりますか?

ある意味で、パスの圧縮は、ランクごとの結合を改善するための追加の手順であり、そのため、その追加の手順を省略しても悲惨な結果を招くことはありません。しかし、ランクによる結合はパス圧縮に必要な中間ステップですか? それをスキップして直接パス圧縮に進むことはできますか?

また、ランクによる結合がなければ、結合が繰り返されると連結リストのような構造が作成される可能性があることも指摘されました。これは、単一パスの圧縮操作がO(n)最悪の場合にかかる可能性があることを意味します。もちろん、これは将来の運用に影響を与えるため、多くの運用で償却したときにこれがどのように機能するかが、私がより興味を持っていることです.

次の図がわかりません。

A が B ではなく D にリンクされているのはなぜですか? C が D ではなく F にリンクされているのはなぜですか?

今日、このスライドの 13 ページのために、Kruskal 最小スパニング ツリー アルゴリズムについて誰かと議論しました。

プレゼンテーションの著者は、(二重) リンク リストを使用して素集合を実装すると、MakeとFindのパフォーマンスはそれぞれ O (1)とO(1 )になると述べています。Union(u,v)操作の時間はmin(nu,nv)です。ここで、nuとnvは u と v を格納するセットのサイズです。

セットの実表現へのポインターを含むロケーターを指す各メンバーの表現ポインターを作成することにより、 Union(u,v)がO(1)になる時間を改善できると述べました。

Java では、データ構造は次のようになります。

ミニマルなコードで申し訳ありません。この方法で作成できる場合、互いに素な集合操作 ( Make,Find,Union )ごとの実行時間はO(1)になります。しかし、私が話し合った人は改善を見ることができません。これについてあなたの意見を知りたいです。

また、さまざまな実装における Find/Union の最速のパフォーマンスは? 私はデータ構造の専門家ではありませんが、インターネットをざっと見てみると、これを行う一定時間のデータ構造やアルゴリズムがないことがわかりました。

多くの要素があり、それらの間の同値関係を追跡する必要があると仮定します。要素Aが要素Bと同等である場合、それは他のすべての要素Bと同等です。

この情報をエンコードするための効率的なデータ構造を探しています。既存の要素との同等性を通じて動的に新しい要素を追加することが可能であり、その情報から、新しい要素が同等であるすべての要素を効率的に計算できる必要があります。

たとえば、要素[0,1,2,3,4]の次の等価セットについて考えてみます。

ここで、等号は同等性を示します。次に、新しい要素を追加します5

等価性を適用すると5=3、データ構造は次のようになります。

このことから、任意の要素に設定された等価性を効率的に反復できるはずです。5の場合、このセットは[3,4,5]になります。

disjoint_setsBoostは、私の要件のほとんどを満たしているように見える、と呼ばれる便利なデータ構造をすでに提供しています。上記の例を実装する方法を示すこの単純なプログラムについて考えてみます。

上で見たように、要素を効率的に追加し、互いに素な集合を動的に拡張することができます。すべての要素を反復する必要なしに、単一の互いに素なセットの要素を効率的に反復するにはどうすればよいでしょうか。

boost :: disjoint_setsを使用する必要がありますが、ドキュメントがわかりません。誰かが各テンプレートパラメータの意味を説明し、disjoint_setsを作成するための小さなサンプルコードを教えてもらえますか？

リクエストに従って、私はdisjoint_setsを使用して、Tarjanのオフラインで最も一般的でない祖先アルゴリズムを実装しています。つまり、値の型はvertex_descriptorである必要があります。