Labyrinth Rekursiv kürzesten Pfad finden?

Habe folgende Aufgabe. Ich soll den Kürzesten Pfad in einem Labyrinth Rekursiv finden.

Bisher kenne ich mich nur mit Wave Propagation (Iterativ) und wallfollower etc aus.

Meine Idee ists nun, dass ich Rekursiv erstmal das Maze entdecke und jedem Schritt eine Distanz zu ordne (Rekursive tiefe).

Nachdem alle Zellen discovered sind gehe ich vom Ziel aus und Suche dort Rekursiv per Backtracking den Kürzesten weg.

Ist das der Richtige Ansatz um das Problem zu lösen?

Das Labyrinth kann auch keine Wände haben und sehr großen Freiraum. Siehe Beispiel:

new String[]{
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "S               D",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
    "                 ",
}

Es wird per Aufgabe zugesichert, dass der Weg maximal 65535 schritte lang ist. Das springt sofort ins Auge, weil unsigned short so groß ist. Dies würde meine Theorie bestätigen wenn man eine unsigned short matrix nehmen würde zum tracken der besuchten Zellen.

Oder gibts da eine bessere Lösung? Hab noch nie wirklich rekursiv gearbeitet und mag Rekursion nicht wirklich bisher.

Answer 1

[apachy]

Hm, ich bin nun kein Experte was Graphen angeht und habe sowas auch nicht während meiner Ausbildung gehabt aber soweit ich weiß macht ein rekursiver Ansatz vor allem Sinn bei einem Depth-First-Search Algorithmus, da dieser mit einem Stack arbeitet, dafür kann man dann natürlich einfach den Callstack Missbrauchen, sprich die Lösung rekursiv lösen.

Das Backtracking erfolgt bei einer Rekursiven Ausführung ja eigentlich auch automatisch, zumindest was dem Fortschritt der Suche angeht. Lediglich vorher gespeicherte Positionen im Pfad müsste man korrigieren, wenn ein Aufruf keine Lösung bringt.

Das Problem bei einem Depth-First-Search Algorithmus ist, dass man ihn eigentlich nicht verwendet um den kürzesten Pfad zu finden, sondern einen Pfad bzw. zur Prüfung, ob es einen Pfad gibt. Dies ist aber nicht zwangsweise der Kürzeste.

Alternativ müsste man den kompletten Graphen durchlaufen und anschließend mögliche Pfade vergleichen in ihrer Länge bzw. während dessen einfach den aktuell kürzesten Überschreiben, was aber sehr zeitintensiv sein kann..

Sprich für so Probleme nutzt man eigentlich etwas wie einen Breadth-First-Algorithmus. Dieser arbeitet aber nicht mit einem Stack, sondern mit einer Queue bzw. Algorithmen, die noch Kosten haben wie Dijkstra mit einer PriorityQueue oder A* wo noch Heuristiken hinzukommen. Da ist Rekursion aber natürlich nicht wirklich nützlich, sofern man nicht nur die Loop damit abbilden will.

Was Rekursion an sich angeht, Rekursion ist toll. Letztlich definierst du oben ein paar Base Cases, sprich ungültige Abbruchbedingungen oder eben deinen Treffer. Der Rest ist dann nur eine Verkleinerung des eigentlichen Problems.

Dies lässt sich dann ebenso leicht erweitern für Dynamic Programming Probleme, bei den z.B. Zwischenergebnisse mit geschliffen werden, für sich wiederholende Teilprobleme.

Woher ich das weiß: Berufserfahrung – Softwareentwickler/Projektleiter seit 2012

Comments

[TheStalker64]

Eine breitensuche hab ich spaßes halber schon implementiert, den Wavepropagation mit ner Queue, der läuft auch verdammt schnell im vergleich zur rekursion. Die tests vom Prof laufen alle innerhalb 0,8s durch. Die derzeitige Rekursive Lösung mit nem Stack brauch viel zu lang für alle Tests. Möglicherweise sind aber die Tests der höheren größen garnicht Pflicht weil Rekursion laaange dauert

Werde nochmal implementieren, wenn der derzeitige pfad schon größer ist als der bereits gefundene pfad, dann bricht er ab