問題タブ [disjoint-sets]

こんにちは、これは私の初めての投稿です、

私は勉強のための質問を考え出そうとしましたが、それを理解することができませんでした：

サイズとパス圧縮による加重和集合を使用した、互いに素なセットの抽象データ型のフォレスト実装を検討します。最初は、各要素は1ノードツリーにあります。

上記の初期状態から開始します。

1. UNIONおよびFIND操作の（短い）シーケンスを指定します。最後の操作はUNIONであり、高いツリーAが短いツリーBのサブツリーになります（つまり、Aの高さがBの高さよりも厳密に大きい）。 。

2. 最後のUNIONがマージする2つのツリーAとBを表示します

ヒント：n = 9個の要素から開始でき、各要素は1ノードツリーにあります。

サイズによる結合のために、小さいツリーは常に大きいツリーとマージされるため、それがどのように機能するかわかりませんか？

ありがとう。

誰かが素集合データ構造とは何かを説明できますか？あるいは、それをうまく説明しているYouTubeビデオまたは記事に私をリンクできますか？

数分前に検索したところ、ベン図のような画像を使った数学のレッスンしか受けられませんでした。たぶんそれだけですが、よくわかりませんので、よろしくお願いします。

簡単に言うと、「バイナリツリーを使用して二項キュー内の各二項ツリーを表す方法」と尋ねられたとき、これは互いに積み重ねる必要のある二項ツリーを指します。B1がB1に接続してB2になるように、2つのB2がB3になり、以下同様に続きます。

これは、素集合の私の Objective-C 実装です。- 親への正数ポイント。- 負の数は、ルートと子の数を示します。(したがって、それらはそれぞれ -1 でバラバラに開始します。) - インデックスは、グループ化するデータとして機能します。問題ないようです... いくつか質問がありました。

1. find:パスを圧縮するにはどうすればよいですか? 私は再帰的に行っていないので、ルートを見つけた後に設定するために、パスを保存して再度ループする必要がありますか?

2. join: 深さではなく、子の数に基づいて結合しています!? それは正しくないと思います。深さが等しい場合、結合中に何か特別なことをする必要がありますか?

ありがとう。

DisjointSet.h

DisjointSet.m

Disjoint set Data Structures と Kruskal のアルゴリズムを OpenCL で実装したいと考えています。OpenCL でいくつかのコードを実装しましたが、OpenCL でデータ構造を開始する方法がわかりません。Aftab Munshi の本に記載されている Djkstra のアルゴリズムは理解しにくいものです。誰かが別の情報源を提案できますか...?

素集合を使用してクラスカルのアルゴリズムの実装を作成しようとしています。ほぼ機能していると思いますが、コードの一部を正しく機能させることができないようです。コードは、グラフ上のノードが、追加しようとしているセットに既に含まれているかどうかを確認する必要があります。それ以外の場合は、追加したくありません。私が使用しているコードは次のとおりです。

ちょっとした情報: このメソッドは、2 つのノードが既に同じセットにあるかどうかを判断しています。ノード配列には、グラフ上のすべてのポイントが含まれます (ノードは、x 値と y 値を格納するだけのクラスであり、それらを取得できます。セットは、ノードの ArrayLists の配列です。問題の開始時に、すべてのノードはArrayList 自体; 最終的に、それらはすべて同じ ArrayList にある必要があります. インデックス 1 と 2 は Nodes 配列のノードに対応します.

残念ながら、このコードでは正しい出力が得られないようです。私はそれを1時間以上見つめていましたが、何が問題なのか理解できませんでした.

前もって感謝します。

これは、今後のテストのための私の練習問題からの質問です。私はこの問題のより効率的な解決策を見つけるのに助けを得たいと思っていました。今のところ、3つの単純なforループを使用するだけでこのタイプの問題を解決できることはわかっていますが、それはそうなるでしょうO(N^3)。

さらに、どういうわけか二分探索を組み込むことが最善の方法であると私は信じており、O(log n)私が探している答えを私に与えてくれます。残念ながら、私はちょっと立ち往生しています。

三者集合の互いに素の問題は次のように定義されます。A、B、Cの3つの集合の項目が与えられた場合、3つの集合すべてに共通の要素がない場合、つまり、次のようなxが存在しない場合、それらは三者素です。 xはA、B、およびCにあります。

A、B、およびCは、注文可能なアイテムのセット（整数）であると想定します。さらに、 O（n log n）時間でn個の整数をソートできると仮定します。O（n log n）アルゴリズムを与えて、集合が3方向集合が互いに素であるかどうかを判断します。

助けてくれてありがとう

最初: 私はそれがプログラミング コンテストの一部であることを認めます (勝つための賭け金などは何もありません)。

問題を読んで次のアルゴリズムを試した後、私は次の結論に達しました。

n頂点の無向連結グラフが与えられた場合、

私はこれを 2 つの方法で実装しました: (1) DFS (2) Disjoint-Set Union ですが、どのアルゴリズムも AC を得るのに十分効率的ではありません。そうするためのさらに良い方法はありますか？詳細な説明は必要ありません。いくつかの単語で十分です。残りは、理解するか、試して死ぬでしょう:p。ありがとう！

私は必須のバックグラウンドを持っており、Haskell で (永続的な) データ構造を作成および変更する練習をするために、単純な素集合 (「共用体検索」) データ構造を実装しようとしています。目標はシンプルな実装ですが、効率性も気になります。私の質問はこれに関連しています。

まず、ランクごとの結合を使用して互いに素な集合のフォレストの実装を作成し、「ポイント」のデータ型を定義することから始めました。

切り離されたセット フォレストは、次のようIntMapにInt → Pointマッピングされます。

シングルトン セットは、その値xから値xを持つ Point への単純なマッピングであり、親はなく、ランクは 1 です。

さて、興味深い部分 – union. この操作は、他のポイントをその親として設定することによってポイントを変更します (場合によってはそのランクを変更します)。Points のランクが異なる場合、はPoint単純に「更新」(新しい Point が作成されます) されて、その親が他のポイントを指すようになります。それらが等しい場合、新しいPointが作成され、そのランクが 1 つ増加します。

さて、私の本当の質問に、もしEQ私が代わりに次のことをしたなら：

つまり、最初にランクを上げた新しいPoint xy'を挿入し、次にの親をランクを上げた新しいPoint xにすると、それらはメモリ内で同じものを指さなくなりますか? Point(これは問題ですか?永続的なデータ構造を使用/作成するときにこれらのことを心配する必要がありますか?)

完全を期すために、次のfindSetとおりです。

(このコードの効率と設計に関する一般的なコメントも歓迎します。)

ユニオン検索を行うために、ばらばらなデータ構造を実装しています。ウィキペディアで次のような記述を見つけました。

... 同じランク r の 2 つのツリーを結合すると、結果のランクは r+1 になります。

ツリーが同じランクであるのに、結合されたツリーのランクを 1 つだけ上げる必要があるのはなぜですか? 単純に 2 つのランク (つまり2*r) を加算するとどうなりますか?

私は、ランダムに選択された3つのばらばらのセットに分割したいマトリックス(200x3)を持っています。どのように私はそれを実現することができますか？

サンプル メソッドを使用して実行しようとしましたが、サンプル メソッドはベクトルのみを受け入れ、出力は実際にはマトリックスの一部ではありません。

したがって、それは私のマトリックスです：

そして、次のように 3 つのセットに分割したい: (行番号はランダムに選択する必要があります)。そして、セットのサイズを指定できるようにしたいです。たとえば、この場合は 4 4 2 です。