Ich habe eine einfache Tiefensuche in Scala mit einer rekursiven Funktion wie folgt geschrieben:
%Vor%wo Labyrinth eine Spezifikation des Problems ist (als Graph oder was auch immer), Pfad ist eine Liste, die den Weg bis jetzt hält und Ziel ist eine Spezifikation des Zielzustandes. Die Funktion gibt einen Pfad zum Ziel als List und Nil zurück, wenn kein Pfad gefunden werden kann.
Die Funktion expandiert z.B. findet alle geeigneten nächsten Knoten (Kandidaten) und muss sich dann rekursiv selbst nennen.
Ich mache das bis
%Vor%Bitte beachten Sie, dass ich einige unnötige Details weggelassen habe. Bis jetzt funktioniert alles gut. Wenn jedoch innerhalb des Aufrufs von foldLeft eine Lösung gefunden wird, wird diese Lösung einfach durch den else-Teil der if-Anweisung kopiert. Gibt es eine Möglichkeit, dies zu vermeiden, indem Sie das FoldLeft aufbrechen oder vielleicht eine andere Funktion anstelle von FoldLeft verwenden? Eigentlich könnte ich wohl eine Version von foldLeft schreiben, die bricht, sobald "not Nil" selbst zurückgegeben wird. Aber gibt es einen in der API?
Ich bin mir nicht sicher, ob ich den Wunsch verstehe, die Schleife kurzzuschließen. Ist es teuer, die Kandidaten zu durchlaufen? Ist die Kandidatenliste möglicherweise groß?
Vielleicht könnten Sie die "find" -Methode verwenden:
%Vor%Wenn die mögliche Tiefe des Suchbereichs groß ist, könnten Sie Ihren Stack überlaufen lassen (passend, da dieser Site-Name angegeben wird). Aber das ist ein Thema für einen anderen Beitrag.
Für kichern, hier ist eine tatsächlich ausführbare Implementierung. Ich musste eine lokale veränderbare Variable (FullPath) hauptsächlich aus Faulheit einführen, aber ich bin mir sicher, dass du diese herausnehmen könntest.
%Vor%Ich mag die Mitch Blevins Lösung, da sie perfekt zu Ihrem Algorithmus passt. Sie könnten an meiner eigenen Lösung zu einem anderen Labyrinthproblem interessiert sein.
Tags und Links scala functional-programming