問題タブ [union-find]

次のアルゴリズムの問​​題を解決しようとしています。

要素を挿入し、最小要素を削除して書き込むことができるデータ構造があるとしましょう。そして、一連のコマンドを知っていると仮定しましょうn。それらはすべてI(k)(k を挿入) またはD(最小値を削除して出力) のいずれかです。

私たちの仕事は、各Dコマンドが返す数値を決定することです。たとえば、シーケンスの場合:

結果は

目標 (またはヒント) は、複雑さよりも優れたものを達成することです。これにより、 でセットの作成、検索、結合O(nlog(n))を行うことができる Find-Union データ構造を使用します。ここで、 は逆アッカーマン関数です。nO(na(n))a(n)

これは宿題ではありません - 私は試験の準備をしていて、すでに数時間以上この演習に苦労しています.

さらなるヒントをいただければ幸いです

編集：重要な仮定を1つ追加するのを忘れていました。挿入するすべての数値は範囲 1..n からのものです

さらに編集：その問題に遭遇したのは私が最初ではないことがわかりました。これはオフライン最小問題と呼ばれ、興味のある人はここでさらに読むことができます

重みのあるエッジのリストがあり、それらから互いに素なセットを取得したいと考えています。ただし、セット内でも重みを追跡したいと考えています。たとえば、データセットがある場合、

2セットになります

基本的に、関係の重みは重みで乗算されます。ブルートフォース以外にこれを追跡するための効率的なアルゴリズムはありますか? 選択した言語は python です。

一般的にユニオン検索を実装する方法は知っていますが、Pythonでセット構造を利用して同じ結果を得る方法があるかどうかを考えていました。たとえば、セットを簡単に結合できます。しかし、セットのみを使用して 2 つの要素が同じセットにあるかどうかを判断する方法がわかりません。それで、通常の実装以外に、そのような操作をサポートするデータ構造がPythonにあるかどうか疑問に思っていますか?

他の同様の質問を調べましたが、このエラーの理由がわかりませんでした。パス圧縮によるランクによるユニオンを使用して、クラスカルの最小スパニング ツリー アルゴリズムを実装する C++ プログラムを作成しています。MST のエッジを正しく出力しますが、パス圧縮部分を含めると、次のエラーが発生します。

* `./kruskal' のエラー: free(): 無効なポインタ: 0x0000000001650d00 *

gdb のバックトレースを見ると、ベクター/クラス デストラクタに問題があるようです。

ループ中にパス圧縮を含めると何が壊れるのか誰か説明してもらえますか?

編集: エラーが発生するサンプル入力:

ユニオン検索アルゴリズムを使用して、無向グラフのすべての接続コンポーネントを検索しています。いくつかの不明な理由により、間違った答えが返されます。私が与える入力グラフは接続されていますが、そのグラフには 2 つの異なるラベルが出力されます。

誰かがこの異常を説明できれば幸いです。Union-Find が機能しない特別な無向グラフはありますか?

** グラフが少し大きいので、グラフを見やすくするために画像を追加しました。グラフをトリミングできませんでした。そうしないと、質問の本質が消えてしまいます。**

ここで、p と rk はそれぞれ親とランクです。

コード

ユニオン機能

検索機能

サンプル入力

グラフの写真

ノード 1、2、3、および 18 とそのエッジは考慮していないことに注意してください。

無向グラフ

私はこのようにアルゴリズムを理解しています...

• パス圧縮により、検索操作の時間が短縮され、パス圧縮の時間の複雑さが平均して O(1) になります。
  

• ランクを見て、2 つのうちどちらが親ノードであるか (ユニオン操作中) を決定します。

しかし、ランクごとの結合が何をするのか理解できませんでした。ここでランクが何を意味するのかを正しく理解しているとは思えません。また、結合する2つのセットのランクが同じ場合、結合中に親のランクが1増加する理由もわかりません。

誰かが答えを太字で説明できますか? それはどのように行われますか？

以下は、次のアップツリーにつながる 4 つの Union-Find 操作 (重み付きユニオンと完全圧縮を使用) のシーケンスです。最後の 2 つの操作は何でしたか?

答え: Union(D,A), Union(B,C), Union(D/A,B/C),Find(B/C).

boost::disjoint_sets_with_storageを理解しようとしていますが、可能な限り単純な例でさえ機能せず、その理由がわかりません。

上記のコードはコンパイルされますが、segfault が発生します。要素として整数を使用したいのですが、ブーストのドキュメントには「要素」テンプレート パラメーターがないため、型を推測すると仮定します。しかし、問題は何ですか？ありがとう

Quick-Findアルゴリズムを使用して、有向グラフ内のすべての弱結合コンポーネントを検索するソリューションを改善しようとしています。

問題文

のリストが与えられた場合、DirectedGraphNodeすべての島 (弱連結成分) を見つけます。

したがって、次の有向グラフが与えられます。

出力は次のようになります (順序は関係ありません)。

Quick-Findアルゴリズムを使用してこれを解決しました。以下のコード:

ただし、このアルゴリズムは最悪の場合、O(N^3)で実行されます。これは、ユニオンの線形検索を毎回行う必要があるためです。これを改善する方法があれば非常に興味があります。

提案ありがとう！

ユニオン/検索構造の「パス圧縮による加重クイックユニオン」アルゴリズムを学習しています。Princeton edu サイトでは、アルゴリズムについて詳しく説明されています。Java での実装は次のとおりです。

しかし、ウェブサイトがそのパフォーマンスについて言及しているように：

定理: 空のデータ構造から開始すると、N 個のオブジェクトに対する M 個の和集合と検索操作のシーケンスは、O(N + M lg* N) 時間かかります。

• 証明は非常に難しい。

• しかし、アルゴリズムは依然として単純です。

しかし、反復対数 lg*n がどのように得られるかについてはまだ興味があります。それはどのように導出されますか？誰かがそれを証明したり、直感的に説明したりできますか?