問題タブ [disjoint-sets]

http://en.wikipedia.org/wiki/Disjoint_sets

http://en.wikipedia.org/wiki/Kruskal's_algorithm

素集合に使用されているデータ構造の結合/検索...

Kruskal のアルゴリズムで使用する Disjoint Sets を実装しようとしていますが、それをどのように行うべきか、特に木の森を管理する方法を正確に理解するのに苦労しています。Wikipedia の Disjoint Sets の説明を読み、Introduction to Algorithms (Cormen et al) の説明を読んだ後、次のことを思いつきました。

ただし、これは不完全であり、何かが欠けていると確信しています。

Introduction to Algorithms は、木の森があるべきだと述べていますが、この森の実際の実装については何の説明もしていません。CS 61B Lecture 31: Disjoint Sets ( http://www.youtube.com/watch?v=wSPAjGfDl7Q ) を見ましたが、ここで講師は配列のみを使用して、フォレストとそのすべてのツリーと値の両方を格納しています。私が述べたように、クラスの明示的な「ノード」タイプはありません。また、この手法を使用している他の多くの情報源 (複数のリンクを投稿することはできません) も見つけました。これはルックアップのために配列のインデックスに依存していることを除いて、喜んでこれを行います.int以外の型の値を保存したいので、何か他のものを使用する必要があります(std::mapが思い浮かびます)。

私がよくわからないもう 1 つの問題は、C++ を使用しているため、メモリの割り当てです。ポインターのツリーを保存しています。MakeSet 操作は次のようになります。 new DisjointSet::Node; . 現在、これらのノードには親へのポインターしかないため、ツリーの最下部を見つける方法がわかりません。ツリーをトラバースしてすべての割り当てを解除するにはどうすればよいですか?

このデータ構造の基本的な概念は理解していますが、実装については少し混乱しています。アドバイスや提案は大歓迎です、ありがとう。

私がこれまでに持っているものは、Cormen et al. による「Introduction To Algorithms」の 571 ページに大きく基づいています。

私はセットを表す Python の Node クラスを持っています:

この実装ではList、ノードの 1 つをフォレストとして使用します (セットを格納するためのより良い方法を受け入れます)。

Initialize()ノードのリストを返します。これを変数に格納setし、他の関数に渡します。

Findは、フォレスト内で値を検索し、それが含まれるセットを返します。for s in range(len(set)):再帰で、 によって渡されるセットのリストを縮小できるように、 を使用することにしましたset[s:]。

Mergeフォレスト内のセットを見つけて、より高いランクのセットを昇格させることにより、セットをマージします。

Finds とsを実行するとエラーが発生しますMerge。つまりFind、適切なセットが返されないため、Mergeも適切に機能しているかどうかわかりません。機能が適切に実装されていることを確認するための助けをいただければ幸いです。

今日が期限の課題について、どのソリューションがリリースされているかについて質問がありますが、正解がわかりません。この質問は、パフォーマンスを向上させるために加重和集合アルゴリズムを利用する素集合フォレストの形式で素集合の最良の場合のパフォーマンスを扱います (ツリーの小さい方のルートは、2 つのツリーのうち大きい方のルートに子として接続されます)。 ) ただし、パス圧縮アルゴリズムは使用しません。

問題は、n 個のシングルトン ノードで (n-1) ユニオン操作を実行し、任意の順序で m>=n 検索操作を実行した場合の最良のケースのパフォーマンスが Omega(m*logn) であるかどうかであり、ソリューションは次のように正しいことを確認します。

n-1 ユニオンのシーケンス S の後に m >= n 検索が続き、Omega(m log n) 時間かかります。シーケンス S は、深さ Omega(log n) のツリーを構築するシーケンス n-1 Unions で始まります。次に、m>=n の検索があり、それぞれがそのツリーの最も深い葉に対応するため、それぞれに (log n) の時間がかかります。

私の質問は、下限が Omega(m*logn) であることを証明するのはなぜですか? それは、境界が Omega(m*logn) であり、すべての入力に対してそれを証明していない場合の孤立した例ではありませんか? 主張を反証するときは反例を1つだけ示す必要があると確信していますが、その正しさを証明するには、可能なすべての入力の述語を証明する必要があります.

私の回答では、2 つのシングルトン ノードを一緒に結合することから始める場合があるという事実を指摘しました。次に、n 個のノードすべてを結合するまで、3 つのノードが同じ親を共有する別のシングルトンをその 2 ノード ツリーに結合し、次に別のノードを結合します。次に、n-1 個のノードがすべて同じ親を指しているツリーができます。これは基本的に、パス圧縮を使用した場合に得られる結果です。次に、すべての FIND が O(1) 時間で実行されます。したがって、(n-1) 個のユニオンと m>=n 個の検索のシーケンスは、最終的に Omega(n-1+m) = Omega(n+m) = Omega(m) になります。

これは、Omega(m*logn) の限界がきつくなく、したがって主張が正しくないことを意味していませんか? Big-O/Omega/Theta を完全に理解していないのではないかと思い始めています :/

編集：質問を修正して、少し明確にしました

EDIT2:これが元の質問の提示方法と解決策です (ガンバリーノと他の男が完全にでっち上げであることに気付くのに少し時間がかかりました; 筋金入りのイタリア人教授)

次のようなウィキペディアによる素集合データ構造を使用して、クラスカルのアルゴリズムをC++で実装しました。

私の質問は次のとおりです。これらの2行のコードが必要ですか？もしそうなら、彼らの重要性は何ですか？

1. int px=findset(x),py=findset(y); 代わりにマージでint px=parent[x],py=parent[y];
2. parent[x]=findset(parent[x]);の代わりにfindsetでreturn findset(parent[x]);

3 つのスレッドがあります。それらのそれぞれは、独自の辞書キーのセットで動作 (読み取り、書き込み) します。したがって、キーは異なるスレッドに対して相互に排他的です。データの読み取りのみを行う複数のスレッドもあります。

次の 2 つのアプローチのどちらが速度の点でより効率的ですか。

1. (ConcurrentDictionary 型の) 単一の辞書を作成する
2. これら 3 つのスレッドのそれぞれに対して、(ConcurrentDictionary 型の) 個別の辞書を作成します。

一見すると、ライターの競合がないため、2 番目のアプローチの方が効率的です。ここに落とし穴はありますか？2 つのアプローチの違いが重要でない場合は、最初のアプローチを使用します。

私のデストラクタは今は良いと思います...しかし、operator（）オーバーロード内からprint_setを呼び出す方法がまだわかりません。

正常に出力されますが、関数呼び出しのオーバーロード内からprint_setを呼び出す簡単な方法があるように感じます...私が望むように物事を取得できないようです。

ヘッダーファイル：

実装：

運転者：

文字列である ID ごとに ID と複数の値を持つ辞書があります。各 Id の各値について、データベースクエリを作成し、設定された結果を取得します。

したがって、各値に対して実行すると、クエリを実行すると別のデータセットが返され、そのセットの各値を選択してクエリを実行すると、別のセットが返され、最終的にアイテムが1つしか返されないポイントに到達します。のすべてのサブ要素の最後の要素を取得したら、Run次に移動しJumpて続行します。

以前にこの質問をしましたが、結果が得られなかったので、コードを削除してもう一度質問するように言われました。これは、私が数日前に尋ねた同じ質問へのリンクです。disjoin set のようなものを実装する必要がありますか?

Connected Component Labeling で Disjoint Sets を使用するのに苦労しています。私は多くの例と、Bo Tian が Disjoint Sets の非常に優れた実装を C++ リンク リストとして提供したこの質問についても調べました。私は自分のプログラムに Connected Component ラベル付け (ラベルは単純な整数) を既に実装していますが、セットがばらばらなラベル間で同等性を解決するのは非常に困難です。

Bo Tianの実装を使用して、誰かが私を助けることができますか? 他の人がこの時点に来たら、それも役立つと思います。

編集

私のアルゴリズムは画像を調べ、異なるラベルを持つ 2 つの接続されたピクセルの 2 つのラベルを見つけると、「等価レジストリ」にメモを作成する必要があります (これは Disjoint set forest になります)。画像全体をループした後、(画像を 2 番目にパスする) レジストリを見て、同等のラベルを持つこれらのピクセルをセットの最小値にマークすることで、同等性を解決する必要があります。

私は3つの文法を持っています:

A -> aB | b | CBB

B -> aB | バ | バ | aBb

C -> aaA | b | タクシー

「各非終端記号の各 RHS の最初のセットを示して、ペアごとに素なテストを実行することにより、[それらが] LL 文法であるかどうかを判断する必要があります。

これは私がこれまでに持っているものです...

A -> aB | b | CBB

最初(aB) = a

最初の(b) = b

最初(CBB) = aaA = a

これは私が問題を抱えているものです。CBBを正しく行いましたか？もしそうなら、それらは交差し、ルールはテストに失敗します。（右？）

B -> aB | バ | バ | aBb

最初(aB) = a

最初の (ba) = b

最初(aBb) = a

それらは交差しているため、ルールはテストに失敗します。

C -> aaA | b | タクシー

最初 (aaA) = a

最初の(b) = b

最初(caB) = c

それらは交差していないため、ルールはパスします