再帰バックトラック迷路の開始と終了をどうやって見つけますか？

Question

再帰バックトラックで生成された迷路の開始点と終了点はどうやって見つかりますか？ 迷路は決してendsなので、それを理解するのは難しいようです。最初にバックトラッキングを開始するのはポイントですか？開始地点は出発地にすることができますが、時にはより良い地点があります。

Answer 1

あなたは、このような再帰的なバックトラックと迷路生成：

http://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking

、すべてのセルが接続されている、そして、あなたのステップを辿りせずに任意の二つのセル間を移動するための一つの方法は、正確にあります。

好きな開始点と終了点を選択できます。

迷路セルのように接続されたグラフは、すなわち、任意の頂点から他の頂点までの正確な経路が1つあるように、無向木であることに留意されたい。最も離れている2つの点を見つけて、開始点と終了点として使用できるようにするには、このツリーの直径を見つける必要があります。

ありことを行う方法の多くが、最も簡単なものは次のとおりです。

1）で開始し、それから最も遠い/頂点を見つけるために、BFSを使用してランダムな頂点を選択します。それがあなたの出発点になります。

2）BFSを使用して、開始頂点から最も遠い/ a頂点を見つけます。それがあなたの終点です。

開始点と終了点はできるだけ離れています。 Proof of correctness: Algorithm for diameter of a tree in graph theory

注意を遠く離れている点が、エッジに限らないこと：それは常に働く理由

この質問への答えは説明しています。 https://mtimmerm.github.io/webStuff/maze.html