問題タブ [union-find]

この質問が少し広範である場合は申し訳ありませんが、最小コストのスパニング ツリーを作成する方法を理解するのに苦労しています。これは、問題がある場合は C++ にあります。

私が理解していることから、クラスカルを使用して、スパニング ツリーを構築するための最小コスト エッジを選択します。私の考えは、エッジを最小ヒープに読み込むことです。そうすれば、最小コストでエッジを取得するためにトップから削除できます。

これまでのところ、minheap と union-find のセットしか実装できませんでした。union-find の目的と、スパニング ツリーを作成するためのソート アルゴリズムについてはまだわかりません。

アドバイスをいただければ幸いです。

編集: ユニオンの検索、minheap、kruskals、および並べ替えアルゴリズムに限定されているわけではなく、何もする必要もありません。これらは講師が提案した項目にすぎません。

有名な素集合データ構造について読んでいたところ、「素集合データ構造か素集合データ構造のどちらかがO(n)時間がかかり、もう一方が時間がかかるO(1)」と書かれていました。

しかし、セットを表すためにビット文字列を使用するのはどうですか？次に、union（ビットORを使用）とfind（セットリストを繰り返して対応するビットがであるかどうかを確認する）の両方1がかかりO(1)ます。

そのロジックの何が問題になっていますか？

多くの問題について、union-find データ構造を使用することをお勧めします。私はそれについて読んで、それがどのように実装されているかを考えてみました (C++ を使用)。私の現在の理解では、それはセットのリストに過ぎないということです。したがって、要素が属するセットを見つけるには、n*log n操作が必要です。ユニオンを実行する必要がある場合は、マージする必要がある 2 つのセットを見つけて、set_unionそれらに対して a を実行する必要があります。これは私にはあまり効率的ではないようです。このデータ構造についての私の理解は正しいですか、それとも何か不足していますか?

連結成分のラベル付けで、左のピクセルと現在のピクセルの上のピクセルの色が同じでラベルが異なることがわかった場合、それらのラベルを同じになるように自動的に再割り当てできませんか (等価テーブルを使用する代わりに) ?

ウィキペディアとMathWorksは現在のピクセルに最小ラベルを割り当てますが、それ以外の場合は隣接するピクセルを同じままにします。次に、別のパスでラベル テーブルを磨きます。私が間違っていない限り、私の微調整により、1回のパスで画像に均一にラベルを付けることができます。ちょっとした調整でアルゴリズムが壊れる例はありますか?

集合論における AUB の一般的な意味とクイック検索アルゴリズムのユニオン操作を関連付けることができません。

Book(Algorithms in C++ Robert Sedgewick) は、和集合操作が「入力ペアごとに配列全体をスキャンする」ことを示しています(コードの 9 行目と 10 行目)。

基本的に、ノードqの値を、ノードpと同じ値を持つ他のすべてのノードにコピーしています。この操作を UNION と名付けたのはなぜですか?

コードは本から直接コピーされます。

Data.UnionFindが IO モナドを使用して、IORef を介してポインターを提供していることに気付きました。unsafePerformIOデータ構造は非常によく理解されているため、純粋なコードでローカルで使用する場合、誰もが喜んで呼び出すと思いますが、..

そのようなデータ構造に対する標準的なよりクリーンなアプローチはありますか? おそらく、unsafePerformIOほとんどのIO操作を禁止することで、避けられない「見た目」の危険性を軽減するIOのラッパーですか？

「パス圧縮による加重クイック ユニオン」アルゴリズムがあります。

コード：

質問:

1. パス圧縮はどのように機能しますか? id[i] = id[id[i]]ルートではなく、ノードの 2 番目の祖先にのみ到達することを意味します。

2. iz[]0からまでの整数が含まれますN-1。セット内の要素の数を知るのにどのようにiz[]役立ちますか?

誰かが私のためにこれを明確にすることができますか?

グラフをノードとエッジのセットとして記述したレコードがあります。

エッジを削除することはないので、接続されたコンポーネントをマップしたいので、union-find 構造 (エッジを追加するときに簡単に更新できます) を使用して接続されたコンポーネントを追跡したいと思います。それらもセットのセットとして保管してください。そしてもちろん、ノードのコンポーネントを取得したいと考えています。

等価ライブラリを見つけました。これを選択したのは、 union-findとpersistent-equivalenceを使用してセットを作成する方法がわからず、値の範囲を知る必要があるためです。

これでリレーションを作成し、以下を使用してセットのセットを返すことができます:

ただし、使用fromListは非常に単純です。内部データ構造からすべての等価クラスを直接取得できるはずです。

さらに重要なことは、データ構造に同値関係を格納するにはどうすればよいかということです。

本当に大きなデータ (2 ^ 32 を超える要素と 2 ^ 32 を超えるペアを結合するなど) 用の拡張された Disjoint-sets アルゴリズムはありますか?

明らかに最大の問題は、そのような大きな配列を作成できないことです。そのため、タスクを達成するためのより良いアルゴリズムまたはより良いデータ構造があるかどうか疑問に思っていますか?

ユニオン/検索構造のクイック ユニオン アルゴリズムを実装しています。「Algorithms in Java」書籍サイト で提供されている実装では、Princeton 実装は (find()メソッド内で) パス圧縮を実装している間、ツリーのサイズ不変を維持できません。これはアルゴリズムに悪影響を与えるべきではありませんか? または私は何かを逃していますか？また、私が正しければ、サイズ配列を変更するにはどうすればよいでしょうか?