Wie finden Sie den Anfang und das Ende eines rekursiven Backtracking-Labyrinths?

Question

Wie finden Sie den Anfang und das Ende eines Labyrinths mit rekursivem Backtracking? Es scheint, als wäre es schwer, es herauszufinden, wie das Labyrinth nie ends. Wäre es der Punkt, an dem Sie zuerst mit dem Zurückverfolgen beginnen? Der Startpunkt könnte sein, wo Sie anfangen, aber manchmal gibt es einen besseren Ort.

Answer 1

Wenn Sie erzeugen ein Labyrinth mit rekursiven Rückzieher wie folgt aus:

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

dann alle Zellen verbunden sind, und es gibt genau einen Weg zwischen zwei Zellen zu reisen, ohne Ihre Schritte zurückzuverfolgen.

Sie können beliebige Start- und Endpunkte auswählen, die Sie mögen!

Beachten Sie, dass ein Graph, der wie die Labyrinth-Zellen verbunden ist, d. H., So dass es genau einen Pfad von jedem Knoten zu jedem anderen Knoten gibt, ein ungerichteter Baum ist. Wenn Sie die beiden am weitesten entfernten Punkte finden möchten, damit Sie sie als Start- und Endpunkt verwenden können, müssen Sie den Durchmesser dieses Baumes finden.

Es gibt viele Möglichkeiten, dies zu tun, aber die einfachste ist:

1) Wählen Sie einen zufälligen Scheitelpunkt an, zu starten und BFS verwenden Sie die/eine Ecke zu finden, die am weitesten von ihm ist. Das wird dein Startpunkt sein.

2) Verwenden Sie BFS, um den Scheitelpunkt zu finden, der am weitesten vom Startscheitelpunkt entfernt ist. Das ist dein Endpunkt.

Die Start- und Endpunkte werden so weit wie möglich auseinander liegen.

Die Antwort auf diese Frage erklärt, warum das immer funktioniert: Proof of correctness: Algorithm for diameter of a tree in graph theory

Beachten Sie, dass die Punkte, die am weitesten voneinander entfernt sind, sind nicht notwendigerweise an den Rändern. Ich finde, dass die Auswahl zufälliger Punkte an den Kanten funktioniert, wenn Sie das brauchen: https://mtimmerm.github.io/webStuff/maze.html