クラスカルのアルゴリズム迷路ジェネレータ

Kruskal のアルゴリズムは、迷路生成に適応できる最小全域木アルゴリズムです。特に、完全な迷路を作成する場合に効果的です。Kruskal のアルゴリズムの代替として、同じく最小全域木アルゴリズムである Prim のアルゴリズムがありますが、どちらも同じ迷路を生成し、Kruskal のアルゴリズムの方が高速に実行されるため、Prim のアルゴリズムを実装する必要はありませんでした。

完全な迷路とは、迷路のどの地点からどの地点へも、ちょうど1本の道がある迷路のことである。つまり、堂々巡りにはならないが、行き止まりにはしばしば遭遇し、引き返してくることを余儀なくされる。

ここで生成される迷路マップには、スタートとゴールの位置がないデフォルトバージョンも含まれています。迷路のどの地点からでも、他のどの地点からでも解があります。インスピレーションを得たい場合は、スタートとゴールの推奨位置を有効にし、その2つの間の解を見ることもできます。

クラスカルのアルゴリズムについて

クラスカルのアルゴリズムは、アメリカの数学者、統計学者、コンピュータ科学者であるジョセフ・バーナード・クラスカル・ジュニアによって考案されました。彼は 1956 年に論文「グラフの最短全域部分木と巡回セールスマン問題について」で初めてこのアルゴリズムを説明しました。

このアルゴリズムは、グラフの最小全域木 (MST) を見つけるように設計されており、サイクルを回避しながら、すべての頂点が可能な限り最小の合計エッジ重みで接続されていることを保証します。

迷路生成におけるクラスカルのアルゴリズムの仕組み

ステップ1: 初期化

• 迷路内の各セルを個別のセット (固有のコンポーネント) として扱います。
• 隣接するセル間のすべての壁を潜在的なエッジとしてリストします。

ステップ2: 壁を整理する

• 壁をシャッフルするかランダムに並べます。真の Kruskal アルゴリズムとして実装する場合は、壁をランダムな順序で並べ替えます (迷路生成には重みは必要ないため)。

ステップ3: 壁を処理する

• シャッフルされた壁を反復します。
• 壁で区切られた 2 つのセルが異なるセットに属している場合 (つまり、迷路内でまだ接続されていない場合)、壁を削除してセットを結合します。
• すでに同じセット内にある場合は、壁をスキップします (サイクルを回避するため)。

ステップ4: 完了するまで続ける

• すべてのセルが接続され、単一のスパニング ツリーが形成されるまで、このプロセスを繰り返します。
• 最後に、すべてのセルはループや分離されたセクションなしで他のセルに接続されます。

Kruskal のアルゴリズムはセットのマージに依存しているため、Union-Find アルゴリズムを使用して最適化できます。このアルゴリズムは、迷路生成中に接続されたセルを効率的に追跡する方法を提供します。Union-Find アルゴリズムの PHP 実装は、こちらでご覧いただけます:PHP での分離集合 (結合検索アルゴリズム)