迷路を作成するには

15461 ワード

tutorial todayilearned beginners algorithms テキストリンク

私は数年前にデータ構造を学び始めた.disjoint-set 私は深い印象を与えたものです、それはとても簡単ですが、エレガントで便利です.
このポストでは、我々はどのように学びますかdisjoint-set そして、我々はそれと迷路ジェネレータを実装します.私は、これが初心者がデータ構造の楽しみを見つけるのを助けることを願います.

非結合集合( union find )データ構造

Disjoint-set 複数の分離(非重複)サブセットに分割された要素の集合を追跡するデータ構造体です.定義によると、2つの分離セットは、その集合が空の集合であるセットです.

上記のイメージで:E 1Set1 そしてE 3 , E 4 , E 5はSet2 .
分離セットには2つの操作があります.union and find , これがdisjoint setも名前で呼ばれる理由ですunion-find :

make_set()    => create a disjoin-set
union(e1, e2) => link 'e1' and 'e2' to the same subset
find(e)       => return the subset's root for 'e'

つの異なるセットから任意の2つの要素を結合する場合、それらは1つの大きなセットにマージされます.
例えば、E 2とE 3が統一された場合、同じセットのE 1とE 5を意味します.

…の結果でfind , つの要素が同じセットに属するかどうかをテストできます.If find(e1) 等しいfind(e2) , このE 1とE 2は同じセットである.
これは、特に、2つのノードが互いに接続性を持っているかどうかをテストする必要があるグラフアルゴリズムに対して、disjoin setの有用なプロパティです.
上記の仕様と説明を考えると、このデータ構造を自分で実装する方法は?
あなたの手でそれを試して数分を過ごすことができますa superior way to study data structures and algorithms .

配列によるナイーブ実装

第一に、データを格納するためのプログラミング言語における基本的なデータ構造を使用する必要がある.つの要素の親を格納することができれば、要素間の関係を保つために木構造を構築することができます.
我々が手術を終えたら、例を挙げましょうunion(e1, e2) , union(e2, e3) , union(e3, e4) , 構築されたツリーはこのようになります(常に最初のパラメータを親として設定したとします).

The find(e) 関数は再帰的なスタイルで実装され、ツリーに従って親を下から上へ見つけるようにします.

#define MAX_SIZE 60
int parent[MAX_SIZE];  // the parent root for each node

void make_set() {
  for(int i=0; i < MAX_SIZE; ++i )
    parent[i] = i;
}

int find(int x) {
  // recursive find and path compression
  if(x != parent[x])
    return find(parent[x]);
  return parent[x];
}

void union_set(int e1, int e2) {
  if( x == y ) return;
  parent[e2] = e1; // e1 is always the parent
}

を、我々は最初のバージョンを終えたunion-find 配列で!
実装の正当性を検証するために、より多くのテストケースを走らせましょうunion(e1, e2) , union(e3, e4) , union(e2, e4) ?

待って!これは我々が期待するものではない!上記の定義によれば、E 1、E 2、E 3、E 4は同じセットであると予想する.の機能にバグがあるようですunion_set .
はい!私たちがしたいことは、2つの要素の親関係だけでなく、union two setです.我々union(e2, e4) , 私たちはE 2とE 4のルートを見つけて、union(e1, e3) .

最初のバージョンのバグを修正しましょう.

void union_set(int e1, int e2) {
  int root1 = find(e1);
  int root2 = find(e2);
  if( root1 == root2 ) return;
  parent[root2] = root1; // e1's root is always the parent
}

ナイーブ実装の時間の複雑さはo ( n )です.

経路圧縮によるCount 1最適化

もっと速くしよう.の正の再帰関数でfind , 再帰的な反復処理で結果をキャッシュした場合、時間のパフォーマンスはずっと良くなります.ここで説明したキャッシュテクニックですCaching: from bottom to top .

int find(int x) {
  // recursive find with path compression
  if(x != parent[x])
    parent[x] = find(parent[x]);
  return parent[x];
}

関数呼び出し後find , ツリーをもっと平らにすることができます(深さが短く、これらの要素の将来の動作を高速化します).

ランク2による組合での1

の最初のバージョンではunion_set , 私たちは常にE 1のルートをE 2の親として設定します.
木の深さは成長し続けるだろう.我々はこれのいくつかの最適化を行うことができますか?ユニオンのランク付けと呼ばれる戦略は、これに役立ちます.
ランク(要素のサブツリーの深さ)を記録するために別の配列を使用する場合は、常に親として深さの大きい要素を設定します.

int rank[MAX_SIZE];    // the depath rank, initialized with 0 in make_set

void union_set(int e1, int e2) {
  int x = find_set(e1);
  int y = find_set(e2);
  if( x == y ) return;

  // optimization with rank
  if(rank[x] > rank[y])
    parent[y] = x;
  else {
    parent[x] = y;
    if(rank[x] == rank[y]) ++rank[y];
  }
}

これを理解する例を挙げましょう.

ランク付けでの作業では、2つの根の深さが等しくない場合、我々は木の深さを成長させないことができます!
もう一つの戦略があるunion by size , これは常に要素を持つ木の根に少数の要素でツリーを結び付けます.
最適化されたバージョンのための時間分析は、多くの数学のトリックが含まれます.
単純に経路圧縮とユニオンによる結論で、結論を出しましょうinverse Ackermann function , α(n)は実際の入力サイズnに対して5未満である.
それは本当に良い時間パフォーマンスです!

メイズジェネレーション

新たに学んだデータ構造を持つ小さなプロジェクトを終えてあなたの学習のための多くの助けを行います.
私が読んだときAlgorithms by Robert Sedgewick , ランダムな迷路をオフセットを生成するための演習があった.
以下のように簡略化されたコードです.

void rand_maze {
  // begin with a rectangular maze of all closed cells
  // numrows = number of rows of cells;
  // numcols = number of columns of cells;
  start = cell at (0,0);
  goal  = cell at (numrows-1, numcols-1);
  numcells = numrows * numcols;
  Partition p(numcells); // p represents the maze components

  // goal is not reachable from start
  while (!p.Find(start, goal)) {
    edge = randomly select a wall;
    x = edge.x;
    y = edge.y;
    if(!p.Find(x,y)) {
      remove edge;
      // x and y now in same component
      p.Union(x,y);
    }
  }
}