問題タブ [union-find]

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

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

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

ありがとう。

DisjointSet.h

DisjointSet.m

coursera のクラスを使用してアルゴリズムを調べてきました。最初の講義の 1 つで、Quick Union Weighted が議論されています。私はそれが何をするかを理解し、彼らのコードを使用してテストし、小さなテストを書きました。

すべてが明確ですが、1 つの点があります。2 つのオブジェクトの結合を作成すると、最小のツリーを持つオブジェクトが最大のツリーに追加されます。同時に、どのツリーが大きいかを決定するために使用される別の配列で、大きい方のツリーのサイズが小さい方のツリーのサイズで増分されます。配列はすべてのインデックスに対して値 1 で開始されるため (基本的に、それ自体のすべてのノードは 1 つのオブジェクトのツリーです)、このインデックスの値が 1 のままではなく 0 に設定されないのはなぜですか?

これを説明するために：

マージされたインデックスのサイズが 0 ではなく 1 になるのはなぜですか? ここでテストするコードを見つけることができます。実装は講師が提供する例と同じであることに注意してください。そのため、私のコードが正しいと仮定しています。

オートマトン アルゴリズムの場合、関数型言語による高速の Union-Find データ構造が必要です。データ構造の正しさを正式に証明する必要があるため、単純な構造を好みます。

私がやろうとしているのはS、関係に関するセット内の要素の等価クラスを計算することR ⊆ S × Sです。最後に知りたいのは、 の任意の要素をその等価クラスの (正規の) 代表にf: S → Sマップする関数です。「標準的」とは、1 つの等価クラスのすべての要素で同じである限り、つまり保持したい限り、どの代表であってもかまわないことを意味します。SRf x = f y ⟺ (x,y) ∈ R

関数型言語でこれに最適なデータ構造とアルゴリズムは何でしょうか? 「通常の」機能コード、つまり可変性/状態変換モナドが本当に必要であることを付け加えておきます。

編集：その間、私はこのアルゴリズムを思いつきました：

Sこれにより、 の任意の要素をその等価クラスの代表にマップするマップが作成されます。ここで、代表は、 の反復によって到達する最初の要素ですS。これには実際には線形時間があると思います（マップ操作が一定の場合）。ただし、これが実際にどれほど効率的であるかがわからないため、他のソリューションにまだ興味があります。

(私の関係は内部的に "S → (S Set) オプション" として表現されているため、{t | (s,t) ∈ R} に対する反復 - これはその構造に対する安価な操作です。)

この問題では std::vector のみを使用しており、各ベクトルは重複せずに並べられています。今、同じ番号を持つベクトルを結合したいと思います。したがって、2 3 は 3 4 5 と結合できますが、4 5 や 1 5 と結合することはできません。

例：

次のベクトルがある場合...

結合後、2 つのベクトルしか残らないはずです。

コード:

目標を達成するために set_union と set_intersection を使用しようとしましたが、期待どおりに動作しません。問題は、適切に変更していないベクトルのサイズにあると思われます。助けてください。ありがとう！

編集：

これはバグのあるコードです。元々はユニオンに問題がありましたが、今は自動的に機能します.. set_intersection を使用して交差があるかどうかを確認する方法がほとんどわからないと思います

各要素の関係を示す N*N ブール対称行列があります。

たとえば、マトリックス

要素 1 が 1、3 と関係があることを意味します。要素 2 は 2、3 などと関係があります。

行列のサイズが大きい (N=9000) ため、要素をクラスター化したいので、ループに 3 つのレイヤーを使用したくなく、代わりにユニオン検索アルゴリズムを使用したいと考えています。

実行コードの場合:

問題は、クラスター ラベルとして常に最小のインデックスを使用したいのですが、コードで正しいラベルが使用されないことがあります。

たとえば、要素 2、3、100 が関連しています。クラスタにラベル 2 を付けたいのですが、ラベル 100 の結果が得られました。誰か論理エラーを教えてもらえますか?

かどうかはわかりません

例えば ​​{1,2,3}->label 1 ;{4,6}->label 4 の場合、union(3,4) を呼び出すと、labels[6] も1に変更？

私は必須のバックグラウンドを持っており、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) を加算するとどうなりますか?