問題タブ [disjoint-sets]

一般に、ランクとパスの圧縮によるヒューリスティックを使用して、互いに素なセットのデータ構造操作を高速に実行します。どういうわけか、重みとパスの圧縮によるヒューリスティックスの方が賢明だと思います。次の実装は、ランクとパスの圧縮によるヒューリスティックと同じ実行時間を達成しますか?

注:構造ノードで使用されるランクは誤称です。ツリーの高さではなく、子の数を指します (ランクは一般的に意味します)。

TopCoder からこの問題を解決したいと思います。この問題では、文字列が指定され、各ステップで、(選択した) 文字のすべての発生を (選択した) 別の文字に置き換える必要があります。回文を取得する手順。問題は、置換の最小総数を特定することです。

これまでのアイデア: 各ステップの後の文字列はグラフの単なるノード/頂点であり、各エッジのコストはステップで行われた置換の数であることを識別できますが、欲張りを使用する方法がわかりませんそれは (最小スパニング ツリーの問題ではないことは間違いありません)。考えられるすべてのノードとエッジ コストを特定し、問題を最短経路問題に変換することは意味がないと思います。反対に、すべてのステップで、文字 X を最大数の競合に置き換え、文字 Y を文字列内で最も多く発生する X と競合するように置き換えることは理にかなっていると思います。

とにかく、それが機能することを証明することもできません。また、これで既知の問題を特定できません。何か案は？

アルゴリズムのクラスで質問を受けましたが、解決できません。質問には、 Theres は を使用したソート アルゴリズムでO(nlogn)あり、検索は二分探索によって行われると記載されていO(log n)ます。2 つの集合が与えられており、2 つの集合が互いに素であるかどうかを判断するアルゴリズムを設計する必要がありますP。Q

disjointsets の find/union メソッドを使用して、無向グラフでサイクル検出のコードを実装しています。

実装は次のとおりです。

これisConnectedが disjoinset の

2 つのノードが同じルート ( によって返されるfind) を持っている場合、サイクルがあることを示します。サイクルがないこのようなグラフの場合(1,2),(2,3),(3,4)、私のメソッドは true を返します。何が悪いのか理解できていません。

最新の編集: 以下の提案の後:

私は得るnode:java.util.NoSuchElementException

Java でこれを自分でコーディングしようとしています...親へのポインターを持つノードを表す GraphNode クラスを作成しました。

また、GraphNode オブジェクトを作成し、その親参照が自身を参照する MakeSet メソッドを含む DisjointSet クラスも作成しました。

問題は、後で Union と FindSet で簡単にアクセスできるように、各ノードをどのように保存すればよいかということです。最初は BST に格納することを考えていましたが、値だけでなく GraphNode への参照も格納するカスタム TreeNode クラスを作成する必要があります。もっと簡単な方法はありますか？

有限集合 S と S の部分集合のリストがあるとします。次に、集合パッキング問題で、リスト内の k 個の部分集合が対素であるかどうかを尋ねます。この問題の最適化バージョンである最大セット パッキングでは、リスト内の対ごとに素なセットの最大数を求めます。

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

だから、しましょうS = {1,2,3,4,5,6,7,8,9,10}

この場合、対素集合の最大数は 3 ( Sa, Sc, Sd ) です。

関連するアルゴリズムに関する記事は見つかりませんでした。同じことに光を当てることができますか？

私のアプローチ：

サイズに応じてセットを並べ替えます。最小サイズのセットから始めます。次のセットの要素が現在のセットと交差しない場合、セットを結合して最大セットの数を増やします。これでよろしいでしょうか？より良いアイデアはありますか？

この問題を解決しようとしていますが、すぐに解決できません。

要するに、グラフ (有向) があり、どのノード (選択するノードのセットが与えられている) から最も多くのノードにアクセスできるかを調べたいと考えています。簡単な実装は、すべてのノードから DFS/BFS を実行し、アクセスできる数を確認することです。しかし、グラフに5000を超えるノードがあるため、遅すぎます。5000 BFS/DFS の実行には非常に長い時間がかかります。

一方で、この問題は Disjoint Set データ構造と関係があるのではないかと感じていますか? しかし、前述のルールのいくつかを分離したセットの実装のように、そのように定式化することはできません。

誰かがこの問題にアプローチする方法についてヒントを与えることができますか?