Labyrinth Rekursiv durchsuchen Performance?
Ich bin dabei ein Labyrinth Rekursiv zu durchsuchen. Klappt auch bei kleinen Labyrinthen.
Code ist folgender, sollte eigentlich selbsterklärend sein denk ich. Problem ist nun folgendes. Der Professor hat viele JUnit Tests geschrieben und bei großen Labyrinthen dauert es zu lang (4s) und bricht daher ab. Wie schreibe ich den Code Performanter? Oder hab ich einen Denkfehler im Code?
Sprache natürlich Java
Ich kann nicht ausschließen, dass die Tests nicht dazu da sind zu erkennen wie performant der Code generell ist. Heißt, dass man guckt wie viele Tests er schafft um zu wissen welche Performance klasse man so etwa hat.
Stack<Coordinate> shortestPath;
private void recursivelyDiscoveryMaze(int x, int y, int depth, Stack<Coordinate> currentPath) {
//this.maze.prettyPrint();
currentPath.push(new Coordinate(x, y));
if (dX == x && dY == y) {
if (shortestPath.size() > currentPath.size() || shortestPath.size() == 0) {
shortestPath = (Stack<Coordinate>) currentPath.clone();
}
currentPath.pop();
return;
}
this.maze.getMazeField()[x][y] = 1; //set visited
depth++;
if (isValidStep(x + 1, y)) //if can be visited
recursivelyDiscoveryMaze(x + 1, y, depth, currentPath);
if (isValidStep(x, y + 1))
recursivelyDiscoveryMaze(x, y + 1, depth, currentPath);
if (isValidStep(x - 1, y))
recursivelyDiscoveryMaze(x - 1, y, depth, currentPath);
if (isValidStep(x, y - 1))
recursivelyDiscoveryMaze(x, y - 1, depth, currentPath);
depth--;
this.maze.getMazeField()[x][y] = 0; //set unvisited
currentPath.pop();
}
2 Antworten
Für eine klare Antwort muss man zu viel raten.
(dX, dY) soll wohl das (einzige) Ziel sein, und du suchst einen kürzesten Weg von einem gegebenen Startfeld dort hin?
Meine Beobachtungen:
- Die beiden Stacks bremsen die Suche sicher gewaltig aus.
- Wenn Du ein Feld nach der Suche wieder auf „unvisited“ setzt, wirst Du die selbe Suche immer wieder durchführen.
Ich denke, dass besonders Punkt 2. zu einer extremen Laufzeit führt. Wenn Du schon Zahlen auf jedes Feld schreiben darfst, kannst Du doch gleich dessen Entfernung vom Start eintragen. Das erspart Dir die Stacks, und Du brauchst ein bereits besuchtes Feld nicht mehr untersuchen, wenn es bereits mit einem kürzeren Pfad erreicht wurde.
Wenn der Algorithmus durch ist, kannst Du einen kürzesten Pfad ganz leicht rekonstruieren, indem Du vom Ziel aus immer auf irgendein benachbartes Feld mit kleinerer Entfernung zum Start wanderst.
Stacks sind teuer − aber nur, wenn sie oft benutzt werden. Der wesentliche Punkt ist ziemlich sicher 2. Wenn Du vermeiden kannst, dass immer wieder die gleichen (Teil-)Pfade gefunden werden, kann es gut sein, dass die Stacks gar nicht mehr so ins Gewicht fallen.
Der Knackpunkt ist, ein Feld nach dem Besuch nicht einfach so wieder freizugeben. Ganz sperren geht aber auch nicht, weil Du ja später mit einer Abkürzung dort landen kannst. Aus dem hohlen Bauch heraus hat ein Feld idealerweise die Zustände:
- wurde noch nie besucht
- wird gerade untersucht
- wurde früher schon besucht und a) führt nach n Schritten zum Ziel oder b) und ist n Schritte vom Start entfernt.
Im Moment behandelst Du 3. wie 1. Mit der Zusatzinfo aus 3. kannst Du aber entscheiden, ob es sich lohnt, die rekursive Prozedur auf diesem Feld zu wiederholen. Mein Bauch sagt zwar, dass 3a) effizienter sein könnte, aber 3b) ist wohl wesentlich einfacher zu implementieren.
Was tut eigentlich die Funktion isValidStep() genau? Ist sie fest vorgegeben oder darfst Du sie ggf. an Deinen Zweck anpassen?
isValidStep darf ich anpassen wie ich will, hab da einmal abfrage ob wall, visited, oder out of bounds.
Die Idee die Strecke zu speichern und nur weiterzugehen wenns n kürzerer weg wäre ist gut, mein Prof hatte mich verwirrt weil ich das vorher so gelöst hatte und dann per rückverfolgung den Pfad suchen.
Werde das mal fix Implementieren, mal gucken ob ich das noch gebacken krieg nach der tortur xD, aber danke
Noch eine Idee:
Die Rekursion kann bei depth>=shortestPath.size() sofort abbrechen. Schon diese eine Abkürzung könnte ausreichen, die Tests zu bestehen.
sicher? Also wir sollen den kürzesten Pfad finden beim 1. überschreiben könnte es doch vllt noch ein etwas schlechterer sein als der echte kürzeste oder? Die Labyrinthe sind manchmal auch einfach nur n großes freie Feld
Habe jetzt folgenden Code, dieser ist bei einem 12x12 Feld aber immernoch extrem langsam (Freies Feld ohne wände) Nach einer Minute kommt nichtmal ein Ergebnis
private void recursivelyDiscoveryMaze(int x, int y, int depth, Stack<Coordinate> currentPath) {
currentPath.push(new Coordinate(x, y));
if (dX == x && dY == y) {
if (shortestPath.size() > currentPath.size() || shortestPath.size() == 0) {
shortestPath = (Stack<Coordinate>) currentPath.clone();
}
currentPath.pop();
return;
}
if(depth>shortestPath.size() && shortestPath.size()!= 0){
currentPath.pop();
return;
}
this.maze.getMazeField()[x][y] = 1; //set visited
depth++;
if (isValidStep(x + 1, y)) //if can be visited
recursivelyDiscoveryMaze(x + 1, y, depth, currentPath);
if (isValidStep(x, y + 1))
recursivelyDiscoveryMaze(x, y + 1, depth, currentPath);
if (isValidStep(x - 1, y))
recursivelyDiscoveryMaze(x - 1, y, depth, currentPath);
if (isValidStep(x, y - 1))
recursivelyDiscoveryMaze(x, y - 1, depth, currentPath);
depth--;
this.maze.getMazeField()[x][y] = 0; //set unvisited
currentPath.pop();
}
sicher?
Ja: Wenn ich einen Pfad mit Länge 1000 kenne, kann ich die Suche nach einem kürzeren Pfad beim 1001. Schritt abbrechen.
Ah hab mich verlesen, ja so hab ichs derzeit gemacht xD
Aber ich glaube die JVM optimiert da auch, denn beim 2. Durchlauf ists um den Faktor 10 schneller
https://ibb.co/Bz0jMVV hier wäre auch nochmal der Callgraph
Okay danke für die Tipps, die Kombination aus dem Zahlen Meer und dem depth>= shortestPath hat die Laufzeit massiv runtergebracht :D
Gratuliere! Aber bei meinen Projekten hat sich die Freude zu oft ins Gegenteil verwandelt, weil eine „kleine Verbesserung“ den Suchraum beschnitten hat und so falsche Ergebnisse produzierte.
Das Zahlenmeer aktualisierst du, wenn du schneller zu der Zelle kommst?
Ich habe mal die Variante getestet, bei der jedes Feld seine Entfernung zum Ziel speichert. Das flutscht in Nullkommanix bis zu einem leeren 82x82-Raum. Darüber läuft der Stack über.
Wenn ich auf ein Feld komme, dessen Entfernung schon bekannt ist, kann ich die Rekursion abbrechen. Allerdings weiß ich dann nicht, wie der Pfad von hier aus weitergeht. Deshalb muss der beste Pfad im Nachgang rekonstruiert werden (oder man speichert den Restpfad in jedes besuchte Feld, was aber etwas Effizienteres als einen Stack erfordert).
Ich vermute, dass diese Methode wesentlich effizienter ist. Wenn Du Zeit und Lust hast, kannst Du ja mal die Laufzeiten vergleichen.
static final int MAX = Integer.MAX_VALUE;
int getField ( int x, int y ) { return maze.getMazeField()[x][y]; }
int setField ( int x, int y, int v ) { return maze.getMazeField()[x][y]=v; }
// Find and store the shortest distance from (x,y) to destination.
// @return shortest distance (0 on destination ... MAX on dead end).
private int recursivelyDiscoveryMaze ( int x, int y ) {
if (getField(x, y) < 0)
return MAX;
if (getField(x, y) > 0)
return getField(x, y);
if (dX == x && dY == y) {
return 0;
}
// getField(x, y) == 0 : first visit && not destination:
setField(x, y, -1); //set visiting
int best = recursivelyDiscoveryMaze(x + 1, y);
best = Math.min(best, recursivelyDiscoveryMaze(x, y + 1));
best = Math.min(best, recursivelyDiscoveryMaze(x - 1, y));
best = Math.min(best, recursivelyDiscoveryMaze(x, y - 1));
return setField(x, y, Math.min(best,MAX-1)+1); //set visited
}
// Create this.shortestPath from (x,y) to destination.
void makePath ( int x, int y ) {
shortestPath.push(new Coordinate(x, y));
final int next = getField(x, y)-1;
assert next < MAX-1;
if ( next ==-1 ) {
assert dX == x && dY == y;
}
else if ( getField(x+1, y)==next ) makePath(x+1, y);
else if ( getField(x, y+1)==next ) makePath(x, y+1);
else if ( getField(x-1, y)==next ) makePath(x-1, y);
else if ( getField(x, y-1)==next ) makePath(x, y-1);
else assert false : String.format("(%3d,%3d)=%3d ⇒ %3d/%3d/%3d/%3d\n"
, x, y, getField(x, y), getField(x+1, y), getField(x, y+1), getField(x-1, y), getField(x, y-1) );
}
und in main():
// statt: maze.recursivelyDiscoveryMaze( x0, y0, 1, new Stack<Coordinate>() );
maze.recursivelyDiscoveryMaze( x0, y0 );
maze.shortestPath = new Stack<Coordinate>();
maze.makePath( x0, y0 );
Das Zahlenmeer aktualisierst du, wenn du schneller zu der Zelle kommst?
Äh, ja. Damit verhindert man, dass die Zelle wieder untersucht wird, wenn man über einen Umweg darauf landet.
Aber mir ging es nur ganz allgemein um das Beschleunigen von rekursiven Suchalgorithmen: Man schneidet ja Teilbäume des Suchraums ab, wenn man weiß, dass sie kein Optimum enthalten.
Nur muss man höllisch aufpassen, nicht versehentlich zu viel abzuschneiden ...
Hier ist mal mein code:
private void recursivelyDiscoveryMaze(final int x, final int y, int depth, final Stack<Coordinate> currentPath) {
if (destinationX == x && destinationY == y) { //check if target reached
shortestPathSize = currentPath.size();
shortestPath = (Stack<Coordinate>) currentPath.clone();
shortestPath.push(new Coordinate(destinationX, destinationY));
return;
}
currentPath.push(new Coordinate(x, y));
this.depthField[x][y] = depth;
depth++;
if (isValidStep(x + 1, y, depth)) //if it can be visited (wall, out of bounds, already visited)
recursivelyDiscoveryMaze(x + 1, y, depth, currentPath);
if (isValidStep(x, y + 1, depth))
recursivelyDiscoveryMaze(x, y + 1, depth, currentPath);
if (isValidStep(x - 1, y, depth))
recursivelyDiscoveryMaze(x - 1, y, depth, currentPath);
if (isValidStep(x, y - 1, depth))
recursivelyDiscoveryMaze(x, y - 1, depth, currentPath);
depth--;
currentPath.pop();
}
Damit brauch ich nichtmal ne rekonstruktion des Kürzesten pfades. Den Findet er immer.
Ist die Sprache da oben C#? Die Getter kenne ich zumindest so aus C# und nicht Java ^^
isValidStep() prüft ob Wand, OutOfBounds und ob der Schritt ein Umweg ist
Ebenso schafft diese version bei mir auch ein 255x255 feld
Ah sehe grad das 255x255 ist bei -Xss256 und nicht default
Ist die Sprache da oben C#?
Nee, Java. Die Hilfsfunktionen sind nur da, damit Du den Code leichter anpassen kannst. Bei mir liegt das Ganze in einer einzigen Klasse.
Ich werde Deine Variante mal bei mir testen.
das 255x255 ist bei -Xss256
Du meinst sicher -Xss256m. Damit komme ich bis knapp 2500×2500. Das dauert dann aber schon 3 Sekunden :-(
Dann scheint dein Code sogar noch schneller zu sein oder? Hast mal beide nebeneinander verglichen?
Wie ich denke ist dein Code erstmal das gesamte Maze erkunden tiefen technisch und dann einfach backtracking die Tiefe entlag gehen oder? So war meine aller erste Idee sogar aber der Prof mochte das nicht so xD Wäre ja ne Art breitensuche oder?
Nee, Java. Die Hilfsfunktionen sind nur da, damit Du den Code leichter anpassen kannst. Bei mir liegt das Ganze in einer einzigen Klasse.
Ja sehe das jetzt auch, hab das garnicht als funktion zuerst erkannt xD
Wie ich denke ist dein Code erstmal das gesamte Maze erkunden tiefen technisch und dann einfach backtracking die Tiefe entlag gehen oder?
Erstmal, es ist Dein Code :) Aber ja, er ist depth-first: Das Labyrinth ist ein Graph mit den Zellen als Knoten mit Kanten zu den Nachbarn links/rechts/oben/unten. Du suchst alle vier Richtungen nacheinander vollständig ab.
Eine Breitensuche würde grundsätzlich anders ablaufen: Hier hast Du eine „Front“ von Zellen, die in depth Schritten erreichbar sind, und erweiterst sie alle um einen weiteren Schritt, bis das Ziel erreicht ist. Das implementiert man leichter in einer Schleife als durch Rekursion. Der größte Vorteil einer Breitensuche ist ihre Laufzeit, die nicht von der Größe des Labyrinths abhängt, sondern nur von der Länge des kürzesten Wegs (hoch 2).
In Deiner Rohversion wird nur durch eine Markierung verhindert, dass man im Kreis läuft. In der Regel wird der Graph dabei in allen vier Richtungen komplett durchlaufen. Das führt zu exponentieller Laufzeit.
Generell gibt es mehrere Ansätze, die Laufzeit zu verringern:
- Symmetrien brechen: Wenn es mehrere „ähnliche“ Lösungen gibt, reicht es, nur eine davon in der Suche zu beachten.
- frühzeitig erkennen, dass man auf dem Holzweg ist, indem man prüft, ob die aktuelle Lösung überhaupt noch zu einem Optimum führen kann.
- Sonderfall: Wenn schon eine (suboptimale) Lösung bekannt ist und die Qualität der Lösung bei der Suche monoton abnimmt, kann man abbrechen, sobald die aktuelle Teillösung zu schlecht wird („Branch&Bound“). Das funktioniert natürlich erst, nachdem man irgendeine Lösung gefunden hat. Deshalb ist hier eine gute Heuristik angesagt, die möglichst frühzeitig eine Lösung findet.
Deine Verbesserung besteht aus der Früherkennung von Mehrfachdurchläufen: Wenn Du schon mal auf einer Zelle warst, musst Du diesen Teilbaum nur dann erneut durchsuchen, wenn Du diesmal mit weniger Schritten hierher gekommen bist. Selbst wenn Deine Reihenfolge links/rechts/oben/unten immer kürzere Wege zum Ziel findet, wird die Suche in tieferen Rekursionen drastisch eingeschränkt, weil jetzt nicht mehr nur der aktuelle Pfad gesperrt wird, sondern es ein „Gedächtnis“ gibt, dass Dir spätere Umwege ersparen kann. Aber ich befürchte, dass die Laufzeit in einem „bösartigen“ Labyrinth immer noch exponentiell sein kann.
Meine Verbesserung funktioniert ähnlich, aber sie hat den Vorteil, dass ich jedes Feld garantiert nur einmal untersuche. Die Laufzeit ist dadurch in 𝓞(#Zellen). Dass ich das Optimum anschließend rekonstruieren muss, nehme ich gern in Kauf, denn jeder Ballast bremst die Suche nur aus. Der einzige Nachteil ist, dass „Branch&Bound“ nicht funktioniert. Dazu müsste ich depth mitführen, und ich befürchte, dass das mehr Overhead als Nutzen bringt.
aber der Prof mochte das nicht so
Er scheint etwas schräge Ansichten zu haben. Eine effiziente Rekursion sollte sich auf das Wesentliche beschränken. Nur so kann man beweisen, dass sie terminiert. Ich würde sogar in Deiner Version den Stack über Bord werfen, weil sie für die Rekursion nicht gebraucht wird.
Hast mal beide nebeneinander verglichen?
Jepp: Dein Code braucht bei mir für 300×300 schon zwei Minuten, meiner schafft 2400×2400 in 3 Sekunden :-P
Okay klingt sehr interessant, werde Mal deine Lösung versuchen exakt zu verstehen im Kopf und dann bei Gelegenheit auch nochmal implementieren um das zu üben, danke :)
Dabei tritt noch eine Frage auf, inwiefern hast du assert benutzt? Ich kenne von meinem Prof nur, dass wir es für n workaround für illegal arguments benutzt haben, damit wir uns damals noch nicht mit exceptions ärgern müssen uns seit neuestem jetzt einfach für interne Fehlersuche benutzen.
Fand es auch eher meh, dass der Prof will, dass man stacks gleich in der 1. Rekursion mitbenutzt, weil viele Veränderungen der Pop/Push Befehle herrschen und das clonen auch nochmal teuer wird. Hab das gemerkt als ich ein Push nach einem If gesetzt hab und es die Laufzeit halbiert hatte oder ähnlich :)
Also hab Mal deine Version implementiert und es scheint nicht immer den kürzesten Weg zu finden, oder ich hab beim Übertragen n fehler gemacht, muss das die Tage nochmal angucken, aber wenn's klappt ist's Aufjedenfall schneller 😂
werde Mal deine Lösung versuchen exakt zu verstehen
Erster Unterschied: Ich teste isValidStep() nicht vor jedem rekursiven Aufruf, sondern am Funktionsanfang. (Randprüfung brauche ich nicht, weil ich das Labyrinth ummauert habe).
Zweiter Unterschied: Ich gebe den kürzesten Abstand zum Ziel zurück (und speichere ihn in der Zelle). Am Ziel gibt's ein „return 0“, und sonst den kleinsten Wert über alle 4 Richtungen plus 1.
Nach der Suche sollte im Start eine positive Zahl stehen, und in mindestens einer Nachbarzelle der Wert um eins kleiner sein, bis zum Wert 0 im Ziel. Diese Strecke laufe ich in makePath() rekursiv ab. Das hätte man auch in einer Schleife abbacken können.
inwiefern hast du assert benutzt?
assert prüft eine Bedingung, ohne die der weitere Programmlauf sinnlos ist (weil es falsche Ergebnisse produziert oder sich aufhängt oder abstürzt).
Die Abbruchbedingung field[x][y]==0 und x=dX && y==dY sind eigentlich äquivalent − außer, ich habe Mist programmiert. Ich prüfe die erste Bedingung, weil die Rekursion da unbedingt stoppen muss − sonst läuft sie in Wände (–1). Das assert dokumentiert hier, dass das Ziel erreicht sein muss, wenn alles mit rechten Dingen zugeht. Falls nicht, ist das Ergebnis sowieso Müll, aber ich erfahre es wenigstens. In so einem Fall würde ich möglichst viel Information in die Assertmeldung dahinter packen und dann das Programm mit derselben Eingabe nochmal starten.
Das else assert false ist ziemlich dreckiger Code. Klar, dass irgendwas nicht stimmt, wenn ich kein passendes Nachbarfeld finde. Das ist in einer ersten Version der Methode tatsächlich passiert, und deshalb steht dahinter auch ein länglicher Fehlertext. Ursprünglich war es etwas wie assert Nachbar-gefunden, aber beim Umstricken der Methode wurde daraus das fünfte else. Und ich wollte einfach nur mit wenig Aufwand meinen schönen Fehlertext behalten ...
nicht immer den kürzesten Weg
Upps, das wäre mir peinlich. Kannst Du ein Labyrinth schicken, bei dem ein falsches Ergebnis kommt?
Ich vermute mal, dass es am Layout liegt:
- Begehbare Zellen haben den Wert 0
- Wände haben den Wert –1
- Alle Randfelder sind Wände
Das Einmauern hab ich mir schon gedacht 😂 fragte mich sonst wie das geht, könnte das Feld eins größer machen.
Werde Mal gucken warum teils falsche Pfade rauskommen, lustigerweise wenn ich mein field printe ist's jetzt plötzlich gedreht 😅 irwas hab ich wohl durcheinander gebracht
new String[]{
"S D",
" ##### ",
" # # ##",
" # # ",
" # # # ",
" # # # ",
" # # ",
" ######## ",
" # # ",
" # "
}
Dort nimmt er 22 schritte statt 10, aber evtl ist meine etwas angepasste version von deinem falsch xD
Oberpeinlich: Wenn ich auf meinen aktuellen Suchpfad stoße, sehe ich den als Wand und notiere daher ggf. eine Sackgasse.
Konkret hake ich den unteren Weg korrekt als Sackgasse ab. Dann biege ich in den mittleren Weg und finde das Ziel. Bei der weiteren Suche laufe ich den oberen Weg rückwärts bis zum Start und denke, das wäre eine Sackgasse.
Tatsächlich müsste ich mich still verdrücken und diesen Weg für spätere Erkundungen (ab der Anstoßstelle) offen lassen.
Ich bin mir nicht sicher, ob der Bug überhaupt reparabel ist. Aber 𝓞(#Zellen) kann ich dann wohl knicken :'-(
Ich werd mal drüber schlafen ...
Ach peinlich ist nichts ^^ passiert ja mal und fällt erst bei vielen Tests auf
Fix: Wenn man Sackgassen nicht markiert, läuft es korrekt:
if (best < MAX) {
return setField(x, y, best+1);
}
else {
setField(x, y, 0);
return MAX;
}
Aber die Laufzeit wird damit bei Sackgassen genau so unterirdisch wie in Deiner Urversion: ein 6×9-Teilraum ohne Hinterausgang ist praktisch nicht mehr lösbar, weil ich dann nichts markieren kann und so effektiv alle Pfade darin enumerieren muss.
Vielleicht kann man das irgendwie reparieren, aber das sprengt den Rahmen. Vergiss meine Variante einfach.
Aber auch bei Deiner Version kann man die Performance mit solchen Labyrinthen testen:
"D# ",
" # ",
" # ",
"S ",
Der Algorithmus läuft zuerst nach rechts in den Nebenraum und durchsucht ihn komplett.
Ich kenne mich nicht gut mit Java aus, aber Rekursion ist immer ein Problem ;)
Zum Einen hast Du ein großes StackOverflow-Risiko und zum Anderen bedeutet ein Methoden-Aufruf Arbeit, die nicht nötig wäre.
Ich würde als erstes überlegen, wie Du die Rekursion raus bekommst.
Und ja, natürlich auch die logische Anpassung, die ralphdieter geschrieben hat :)
Habe Wavepropagation vor 2 Jahren schonmal gemacht und der läuft alle tests innerhalb 0,8s durch, also verdammt gut wohl. Die Aufgabe MUSS leider Rekursiv gelöst sein
Also das mit 2 Stacks hat mir der Prof so empfohlen, sagte aber auch, dass die sehr atmen und das sehr teuer wird.
Punkt 2 verstehe ich nun so, dass man immer die Distanz updated, also eher das Feld rekursiv erforscht und dann nur noch rückwärts sucht nach dem weg (distanz-1) richtig? So schlug ich es ihm auch vor und dann brachte er das mit den 2. Stacks auf, weil das "echt" rekursiv wäre und besser trainiert.
Und ja dX, dY sind die Coordinaten des Ziels ^^