古典的な迷路生成アルゴリズム。 パート2：チャンスに飛び込む

まえがき

→ 前半



だから。 Habrオーディエンスの反応を評価し、問題を整理し、サイクルの2番目の記事を書き始めました。 大衆の反応は私の想定よりもはるかに肯定的でした。つまり、手続き生成の最も興味深いトピックの1つである迷路の作成について会話を続けています。



このパートでは、ランダムおよび擬似ランダム生成とは何か、アルゴリズムは互いに同等に異なる迷路を与えることができるもの、およびそれらの不利な点について説明します。 今日の冒険のヒーローは、ウィルソンアルゴリズムとランダムスパニングツリー（均一スパニングツリー）を作成するためのAldous-Broderアルゴリズムです。 注意トラフィック 。



問題の理想的な迷路が何であるかを思い出しましょう。 グラフの各頂点から他の頂点まで正確に1つのパスがあり、同じエッジを2回通過せずにすべての頂点を通過できない場合、このようなグラフをスパニングツリーと呼びます 。 各セルから他のセルへの検討中のラビリンスで、正確に1つの通路があり、同じ廊下を2回通過することなくすべてのセルを訪れることができない場合、そのようなラビリンスが理想的であると言います。 意味は1つの簡単な理由で変わりません。迷宮はグラフであり、前の記事で書きました。 まだ読んでいない場合は、先に進む前にもう少し上にスクロールし、リンクをたどってそれをよく理解することを強くお勧めします。



また、このパートで紹介するアルゴリズムは非常に低速で「愚かな」ものですが、トピック全体および私のすべての記事の基盤であるため、対処する必要があります。 私がすぐに彼らから始めなかった主な理由は、ウィルソンは初心者にとって非常に簡単に実装および理解することができず、それが彼の極端な好奇心を妨げるものではないからです。

変位とランダム性

ランダム生成とはどういう意味ですか？ 2番目のラビリンスで、1番目とは異なり、南に2つの壁がない場合、それらは完全にランダムであると言えますか？ または、最初の迷路にさらに2つの水平通路がある場合はどうでしょうか？ はい、いいえ。



ラビリンスのランダム性といえば、私たちが何を意味するのかを明確に認識しなければなりません。 二分木アルゴリズムの結果を見てみましょう：











ご覧のとおり、ラビリンス自体は完全に異なりますが、変位はわずかに異なります。



ランダムな結果が得られましたか？ はい 彼をそのように考えることはできますか？ まあ、私の意見では、いいえ。



問題はバイアスであり、これが主に「ランダム性」を決定します。 定義上、ランダムな迷路を作成し、最終的に同様の迷路を作成するアルゴリズム。 バイナリツリーのように「類似性」が発音される場合、そのような迷路は簡単に解決されると言います。 いくつかのラビリンスを比較するときに、アルゴリズムが何に引き付けられるかを明確に言うことが難しい場合、そのようなラビリンスを解決するのはより難しいと言います。 バイアスを見つけるには、生成のいくつかの結果を比較し、このタイプの迷路を解決するために、よりスマートなパスまたは自分自身の検索を作成できる統計モデルを構築する必要があります。 たとえば、二分木アルゴリズムには、垂直方向の通路のn倍の水平方向の通路があると言えます。 これは、データを考慮に入れて、出口を見つけるプロセスを高速化できることを意味します。



しかし、バイアスをまったく必要としない場合はどうでしょうか？ たとえば、グラフの接続されていない9個のポイントから、他とはまったく異なるスパニングツリーを取得するたびに、 次に、アルゴリズムの各方向が同等になる必要があります。 これは、すでに完了したピークを通過できることを意味します。したがって、サイクルの各反復で、そこにいたかどうかに関係なく、4つの方向のいずれかをランダムに選択します。 唯一の条件は、フィールドを超えないことです。



用語ユニフォームスパニングツリーといえば。 スパニングツリーが何であるかは既にわかっています。 グラフのすべての頂点をエッジで接続し、同じエッジを2回通過せずに頂点から別の頂点に到達できないようにすると、スパニングツリーが作成されます。 しかし、グラフに3つ以上の頂点がある場合、さらに多くのツリーバリエーションがあるかもしれません。 そのため、均一スパニングツリーは、特定のグラフにおけるスパニングツリーのバリエーションの1つです。



など。 互いに完全に異なる完全にランダムなラビリンスが必要であり、速度を犠牲にする準備さえできています。 それでは、Aldous-BroderアルゴリズムとWilsonアルゴリズムについて理解しましょう。

Aldous-Broderアルゴリズム

説明



二分木アルゴリズムが最も理解しやすいと言ったことを覚えていますか？ だから、私はcでした。 常に考慮しているのは1つの方向と1つの側面のみを扱うため、実装は非常に簡単ですが、原始性と「愚かさ」ではAldous-Broderアルゴリズムがはるかに進んでいます。 その全体のポイントは、作成されるスパニングツリーの上部につまずいて別のポイントを取り付けることを期待して、フィールドをあちこち歩き回り、再びランダムに迷路のポイントを選択し、接続されたものの1つに入るまで歩くことです。



Aldous-Broderにはバイアスがありません。 絶対に。 その助けを借りて得られた迷路はすべて完全にランダムであり、似ていません。 アルゴリズムには、方向性、エンタングルメント、またはその他の特性の好みはありません。 結果のラビリンスはランダムであり、同様に発生する可能性があります。



問題は、乱数ジェネレーターの欠陥である可能性があります。乱数ジェネレーター自体は、いくつかの値に引き寄せられ、より頻繁に値を与える場合があります。 しかし、たとえば、自然ノイズ（風、ウラン崩壊）に基づいたランダムジェネレーターを使用する場合、おそらく、アルゴリズムの操作を最終的に完全に楽しむことができます。



確かに、彼の作品を観察することは、存在のすべての腐敗性と無意味さの真の認識を与えます。 彼は5×5のフィールドで30秒に収まりたくなかったため、アニメーションでgifを記録するのに多くの時間を費やしました。 最後の1つの未チェックのセルのみをスパニングツリーに接続し続けると、Aldous-Broderは別のコーナーに行き、そこで円をラップしました。 最終的に彼は迷路のすべてのセルを回ることができるように、アニメーションの速度を大幅に上げ、フィールドを減らす必要がありました。



これは、スパニングツリーの同等の可能性のある変種を研究した2人の独立した研究者によって作成されました。カリフォルニア大学バークレー校の教授であるDavid Aldousと、現在Googleで働いている科学者のAndrei Broderです。 これらの研究がどの分野で役立つかを明確に言うことは困難です。 ただし、ラビリンスに加えて、アルゴリズムは数学的な確率の研究でしばしばポップアップしますが、その動作原理を考えると驚くことではありません。



正式なアルゴリズム：

1. ランダムな頂点（セル）を選択します。 完全にランダム。
2. ランダムに隣接する頂点（セル）を選択して、そこに進みます。 訪問されていない場合は、ツリーに追加します（前のツリーに接続し、それらの間の壁を削除します）。
3. すべてのセルが表示されるまで手順2を繰り返します。

長所：

• バイアスはありません。
• ラビリンスは完全にランダムであるため、それらを解決するための特定のアルゴリズムを作成することはできません。
• その人の決定の複雑さ。
• 簡単な実装。

短所：

• スピード。 迷路が生成される間、あなたは年をとって死ぬ時間があるでしょう。
• 無限の迷路を生成することはできません。
• 発電終了時の効率の大幅な低下。

ウィルソンアルゴリズム

説明



おめでとう、私たちはついにもっと深刻な何かに到達しました。 ウィルソンのアルゴリズムは、実装と理解の両方において、以前のアルゴリズムよりもはるかに複雑です。 ウィルソンの目標は、彼の愚かなパートナーであるAldous-Broderの目標のように、同様に確率の高いランダムなスパニングツリーを生成することです。 動作原理は多少似ていますが、詳細は大きく異なります。



このアルゴリズムは、迷路（グラフ）の移動側のランダムな選択に等しく基づいていますが、2つの重要な違いがあります。



フィールド内を移動して、スパニングツリーの頂点が見つかる前に訪れたすべての頂点を「記憶」します。 既に追加された頂点に出会うとすぐに、生成されたツリーに結果のサブグラフ（ブランチ）を添付します。 サブグラフにループが作成されている場合は、削除します。 ループとは、一時的なサブグラフにすでにある頂点と、別のポイントにある頂点との接続を意味します。 つまり、頂点が2つを超える頂点があってはなりません。 あなたが今理解していないなら、それは怖くありません-あなたは仕事の例でさらに明確に見るでしょう。



サブグラフをスパニングツリーにアタッチした後、次のランダムポイントの選択は、まだアタッチされていない頂点からのみ発生します。 その結果、Aldous-Broderとは異なり、ウィルソンには、すでに処理されたピークをあてもなくさまようという不利な点がありません。



Aldous-BroderのようなWilsonのアルゴリズムは、偏りのない完全にランダムなラビリンスを生成します。 アルゴリズムには、方向性、エンタングルメント、またはその他の特性の好みはありません。 残念ながら、最良の結果を得るには、数値の設定がないハードウェア乱数ジェネレーターを使用する必要があります。



アルゴリズム自体は、1996年に、David Wilsonによって、等確率のランダムスパニングツリーの生成に関する論文で公開されました。 前と同様に、迷路に加えて、数学的確率に専念するさまざまなサイトに資料がポップアップ表示されます。 さらに、特に均一スパニングツリーとウィルソンアルゴリズムに関するいくつかの興味深い出版物に出会いました。 それらの1つでアルゴリズム自体がより詳細に説明されている場合、もう1つでは全体として概念自体とスパニングツリーの数学的基礎が説明されています。



読者が興味を持ったら、おそらくパート2aを書きます。そこで、作品自体とその部分的な翻訳を引用します。 ここで数学的な正当化を避ける主な理由は、私の記事が初心者や乾式数学よりもプログラミングに興味がある人を対象にしているからです。



正式なアルゴリズム：

1. スパニングツリーに属さないランダムな頂点を選択して、ツリーに追加します。
2. スパニングツリーに属さないランダムな頂点を選択し、ツリーに既に追加されている頂点に到達するまでグラフの移動（迷路）を開始します。 サイクルが形成された場合、それを削除します。
3. 結果のサブグラフのすべての頂点をスパニングツリーに追加します。
4. すべての頂点がスパニングツリーに追加されるまで、手順2〜3を繰り返します。

長所：

• バイアスはありません。
• ラビリンスは完全にランダムであるため、それらを解決するための特定のアルゴリズムを作成することはできません。
• その人の決定の複雑さ。
• 意味のない放浪はありません。
• Oldos-Broderと比較した速度は数倍です。

短所：

• 難しい実装。
• 生成の開始時に速度が低下します。
• Aldous-Broderよりも大きなメモリ要件。

エピローグ：

上記のすべてを要約すると、より複雑なアルゴリズムに着手し、グラフのいくつかの（いくつかの）概念を見つけたが、主な困難はまだ来ていないことに注意する価値があります。 Eller、Kraskal、Primの明らかに紛らわしいアルゴリズムは、グラフとツリーの操作のみに基づいており、興味深いとはいえ、難しい出版物を準備しています。 ただし、それらを書き始める前に、リターンサーチアルゴリズムと、「Catch＆Kill」と呼ばれるものを見てください。迷路を生成する作業は他のすべてとは非常に異なります。 次の記事についてヒントを与えました。



他に何。 前の部分へのコメントで、一部の人々は彼らの生成アルゴリズムを尋ねたり捨てたりしました。 独自の方法でラビリンスの作成を一度実装し、今すぐ覚えることができる場合は、共有してください。 おそらく、あなたの許可を得て、私が彼について書く記事のいくつかで。 一般的に、私はこのトピックに関する興味深い話や思い出に満足しています。 学校のノートブックや大学のコンピューターで迷路を描く方法を覚えていても構いません。



まあ、そしていつものように。 願い、批判、コメントはいつでも歓迎します。トピックが気に入って次のパートを見たい場合は、コメントに書いてください。



Lua +のアルゴリズムのソース+ Love2Dでレンダリング（コメント内のリクエストでコードがレイアウトされます。リファクタリングされません）：

Github