4

標準の素集合構造は非結合をサポートしていないため、結合、検索、および非結合をかなり効率的にサポートできるデータ構造を探しています (すべて少なくとも O(log n) 以上)。背景として、私は MCTS [ http://en.wikipedia.org/wiki/Monte_Carlo_tree_search]を使用して Go AI を作成しています。これは、バックトラック中に接続および切断される石のグループを追跡するために使用されます。デユニオンはセット内の任意のオブジェクトではなく、常に最新のユニオンの「元に戻す」ため、これにより簡単になると思います。

私は次の論文を読みましたが、提案されたデータ構造を実行することはできましたが、少しやり過ぎで、 http://docs.lib.purdue.edu/cgi/viewcontent.cgi ?article を実装するのに時間がかかるようです。 =1773&context=cstech

もちろん、O( a(n)) は素晴らしいものですが、パス圧縮は de-union では機能しないと確信しており、O(log n) に満足しています。私の腸は、解決策がヒープに関連している可能性があることを教えてくれますが、何も理解できませんでした.

4

1 に答える 1

6

あなたが説明していることは、union-find-split 問題と呼ばれることもありますが、最新のデータ構造 (または少なくとも私が知っているもの) では、通常、この問題を別の方法で見ています。すべての要素をフォレスト内のノードと考えてください。次に、操作の下でフォレストを維持できるようにしたい

  • エッジ (x, y) を追加するリンク(x, y)、
  • x を含むツリーの代表ノードを返すfind (x)、および
  • cut (x, y) は、エッジを x から y にカットします。

これらのデータ構造は、動的ツリーまたはリンクカット ツリーと呼ばれることがよくあります。私の知る限りでは、標準の共用体検索データ構造の実装の単純さに匹敵する効率的なデータ構造はありません。あなたの場合に役立つかもしれない 2 つのデータ構造は、リンク/カット ツリー (Sleator-Tarjan ツリーまたは ST ツリーとも呼ばれます) と Euler-tour ツリー (ET ツリーとも呼ばれます) です。上記の操作の時間 O(log n) それぞれ。

お役に立てれば！

于 2014-09-10T01:51:17.223 に答える