Math
Breite und Tiefe
Zwei Kopien eines Labyrinths, zwei Durchläufe, eine Zelle pro Takt. Die Schicht, in der die Breitensuche eine Zelle findet, IST der kürzeste Abstand - eine Identität. Die Tiefensuche ist nie kürzer, und wie viel länger, hängt vom Ziel ab.
Was passiert
Ein Labyrinth, zwei Suchen, eine Entdeckung pro Schritt. Links nimmt die Breitensuche Zellen aus einer WARTESCHLANGE - wer zuerst kommt, geht zuerst -, darum breitet sie sich in Ringen aus, und der Ring, in dem sie eine Zelle findet, ist deren kürzeste Entfernung: In einem ungewichteten Labyrinth IST die Breitensuche die Suche nach dem kürzesten Weg. Rechts nimmt die Tiefensuche sie von einem STAPEL - wer zuletzt kommt, geht zuerst -, darum taucht sie in die erste Abzweigung und kehrt nur an einer Sackgasse um; ihr Weg ist ein Weg, ohne Versprechen, kurz zu sein. Blaue Zellen warten in der Struktur, graugrüne sind fertig, das goldene Quadrat wird gerade erweitert, und unter jedem Labyrinth stehen die echte Warteschlange und der echte Stapel, die nächste Zelle zuerst. Zeichnen Sie Wände, klicken Sie in ein Labyrinth, um vorherzusagen, wohin diese Suche als Nächstes geht, und machen Sie einen Schritt. Ist das Ziel abgemauert, enden beide Suchen am Rand der Komponente des Starts und sagen es.
Gleichungen des Moduls
Gleichungen Labyrinth auf einem m x m Gitter, vier Nachbarn, Start in der linken oberen Ecke; Nachbarreihenfolge oben, rechts, unten, links - in beiden Suchen gleich Breitensuche: die Schicht, in der eine Zelle gefunden wird, IST die Länge des kürzesten Weges - eine Identität, geprüft gegen eine UNABHÄNGIGE Relaxation bis zum Fixpunkt und, auf kleinen Gittern, gegen eine vollständige Aufzählung einfacher Wege leeres Gitter: Abstand zu (i, j) = i + j; Zellen im Abstand d = min(d, m−1) − max(0, d−m+1) + 1; breiteste Schicht = m bei d = m − 1; fernste Ecke = 2(m−1) = 40 bei m = 21 beide Suchen überdecken dieselbe Menge - die Komponente des Starts, unabhängig durch eine Union-Find-Struktur gezählt - und jede betrachtet jede Kante zweimal: 2|E| = 1196 bei 21x21 mit 20 % Wänden Tiefensuche ist nie kürzer, und wie viel länger, hängt von der ZELLE ab: zur fernsten Ecke eines leeren Gitters braucht sie dieselben 2(m−1) Schritte, zur Zelle einen Schritt unter dem Start braucht sie 421 bei m = 21 auf einem leeren Gitter ist der Tiefensuchbaum ein HAMILTON-PFAD - jede Zelle hat höchstens ein Kind, die tiefste liegt bei m²−1, und die Parität entscheidet, wo die Schlange endet: (1,0) für gerades m, (m−1,0) für ungerades m 21x21, 20 % Wände, Ziel in der fernsten Ecke: Breitensuche 40 Schritte nach Berührung von 370 Zellen; Tiefensuche 50 Schritte nach Berührung von 53 - beide zahlen, in verschiedener Währung dasselbe Labyrinth, Ziel in der Mitte: Breitensuche 20, Tiefensuche 156; und auf 297 der 371 erreichbaren Zellen ist der Tiefensuchweg mindestens dreimal so lang
