問題タブ [union-find]

クラスター化したい 5 つのセットがあるとします。ここで説明されている SimHashing 手法を理解しています。

https://moultano.wordpress.com/2010/01/21/simple-simhashing-3kbzhsxyg4467-6/

たとえば、結果が次の場合、3 つのクラスター ( {A}、{B,C,D}および) が生成されます。{E}

同様に、MMDS ブックの第 3 章で説明されている MinHashing 手法:

http://infolab.stanford.edu/~ullman/mmds/ch3.pdf

その結果が次の場合、同じ 3 つのクラスターを生成することもできます。

(各セットは、3 つの「バンド」で構成される MH シグネチャに対応し、シグネチャ バンドの少なくとも 1 つが一致する場合、2 つのセットがグループ化されます。バンドが多いほど、一致する可能性が高くなります。)

ただし、これらに関連するいくつかの質問があります。

(1) SHは MHのシングルバンド版と理解できますか?

(2) MH は、クラスターを構築するために Union-Find のようなデータ構造を使用することを必然的に意味しますか?

(3) クラスターは、両方の手法で、実際には「候補ペア」のセットであるという意味で、実際には「クラスター前」であると考えるのは正しいですか?

(4) (3) が真の場合、O(n^2)「実際の」クラスターにさらに分割するために、各「プレクラスター」内で検索を行う必要があることを意味しますか? (これは、小さくてかなりバランスの取れた事前クラスターが多数ある場合は合理的かもしれませんが、それ以外の場合はそれほど多くありません)

クイック結合の改善に関する Robert Sedgewick のビデオを見ていました。( https://youtu.be/sEo6LlPxPHE?t=267 )

そこでは、高さではなく木のサイズを使用しています。実際、問題はルート ノードを見つけることです。高さが高いと見つけにくい。そのため、高さの影響を軽減する方法を見つける必要があります。高さを比較するだけでは、期待どおりに機能しませんか? より短いツリーをより高いツリーに接続しても問題は解決しません:ノード数の少ないツリーをノード数の多いツリーに接続しますか?

次の場合はどうですか？

ビデオのロジックによると：

A ツリーのサイズ = 4

B ツリーのサイズ = 7

A を B に接続する場合。実際には、結果のツリーを高くしています (高さ 4)。しかし、木の高さに基づいてそれを行っていれば、木 B を A に接続することで解決できたはずです。したがって、結果のツリーの高さは 3 になります。

私は正しいですか？間違っている場合、どこが間違っていますか?

基本的に、頂点 u と v が同じコンポーネントにないかどうかを確認する以外に、もう 1 つの条件を追加して、クラスカルのアルゴリズムを変更しようとしています。ユニオン検索データ構造がどのように機能するかを漠然と理解しているので、実際に正しい考えを持っているかどうかを確認したかった.

無向グラフ G = (V, E) と、V のいくつかの頂点 (頂点 A ⊂ V のサブセット) を含む集合 A があるとすると、V の頂点 u ごとに (ループ) 、u もこのセット A に含まれています。

設定されたパラメーターが異なる (つまりラベルが異なる) ため、これは機能しませんか? 確認したかっただけなのに…

明確にするために、エッジ (u, v) にセット A の頂点の 1 つが含まれているかどうかを知る必要があります。そして、これを達成するために Union-Find を使用しようとしていました (find() には O(1) 時間がかかるため)。セット A をトラバースして各要素を比較する代わりに...これが可能かどうか誰か教えてもらえますか? それとも、配列トラバーサル メソッドを使用する必要がありますか?

ありがとうございました。

(A,B) の形式で複数のタプルが与えられた場合、A は親、B はバイナリ ツリーの子であり、入力が有効かどうかを調べます。4 つのエラー条件が提供されました。

1. 親に 2 人以上の子供がいる場合、
2. 重複したタプルが入力された場合、
3. 木に循環がある場合、
4. 複数のルートが可能な場合。

複数の有効条件に違反する場合は、上記の順序で最初に来る条件を出力します。入力が有効な場合、ツリーをシリアル表現で出力します。例: 入力が (A,B), (B,C), (A,D), (C,E) の場合、出力: (A(B(C(E)))(D))

ユニオン検索データ構造で解決しようと考えていますが、コーディングできません。c / c ++のロジックまたは疑似コードで誰かが私を助けてくれますか

次のデータセットがあります

ユニオン検索を使用して 5 が 7 に関連しているかどうかを判断するにはどうすればよいですか? 誰か私を導いてください。