Wie würde ich das Äquivalent des folgenden Pythons in clojure codieren, aber strikt die Rekursion für die Stapelverwaltung verwenden (zB keine Schleife verwenden/rekurrieren mit einem Vektor als Grenze)? Mir ist klar, dass es ziemlich einfach ist, wenn ein Vektor deine Pfade pflegt und nur späht/knallt, aber ich tue dies als Gedankenübung.Wie implementiert man ein rekursives DFS in Clojure (ohne Verwendung eines Vektors/Stacks)
Python Version
def dfs(start,successors,goal,visited=set()):
if start not in visited:
visited.add(start)
for s in successors.get(start):
if goal(s):
return s
else:
res = dfs(s,successors)
if res: return res #bail early when found
return False
Clojure Version
(defn dfs [start goal? successors visited]
(if (goal? start)
start
(when (not (contains? visited start))
(mapcat #(dfs % goal? successors (conj visited start))
(successors start)))))
Da Iteration durch einen Aufruf gesteuert wird, in der Clojure Version abzubilden, können Sie nicht wirklich früh auf die Art, wie du c ein in Python z.B. if goal(s): return s. Da Sie die rekursiven Aufrufe innerhalb einer Liste mit Map sammeln, müssen Sie jeden möglichen Knoten auch nach dem Fund des Ziels überprüfen. Erst dann, wenn alle Knoten erkundet sind, erhalten Sie das Ergebnis.
Jetzt weiß ich, dass ich so etwas tun kann (ich weiß, dass das nicht schön ist ... versuche nur ein kurzes Beispiel zu geben, zögere nicht, Verbesserungen vorzuschlagen!), Aber ich bin hauptsächlich daran interessiert zu sehen, ob es da ist eine Möglichkeit, die Verwendung eines Stacks explizit zu vermeiden und den Call-Stack wie in der Python-Version arbeiten zu lassen.
(defn dfs-non-rec [frontier goal? successors visited]
(loop [f frontier g? goal? s successors v visited]
(let [node (peek f)]
(cond ; case 1
(goal? node)
node
;case 2
(not (contains? v node))
(recur (vec (concat (pop f) (successors node))) g? s (conj v node))
;case 3
:else
(recur (pop f) g? s (conj v node))))))
Wie soll ich das angehen?
EDIT
Es gab einige Verwirrung meinerseits, ob einige der Antworten waren in der Tat zuerst in die Tiefe. Die Verwirrung rührte von einer Annahme her, die ich über die Eingabe gemacht habe, die ich ursprünglich in diesem Beitrag hätte geben sollen. Ich hatte den Eingang als Adjazenzliste angenommen, das eine Graph, anstatt ein Baum
(def graph {"a" ["b","c","d"],
"b" ["a","e","f"],
"c" ["x","y"],
"d" [],
"e" [],
"f" [],
"x" ["c"],
"y" ["e"]})
dann dar, wenn auf eine seq umgewandelt, gefolgt ist die Reihenfolge in-fact depth-first für dass Der sich ergebende Baum wird durch Aufrufen von seq auf dem Graph erstellt, jedoch wird die Reihenfolge, die durch die Adjazenzliste impliziert ist, nicht befolgt, da die Graphstruktur in der Konvertierung verloren geht.
Also, wenn Sie für den Knoten x ab dem a suchen, würde ich die Traversierfolgeliste erwarten adcyex zu sein, anstatt abcdbaefcxy
Ich bin mir nicht sicher, ob ich über die Prüfung für Zyklen Teil zustimmen. Selbst mit unveränderlichen Strukturen können Sie immer noch Grafikzyklen haben. wenn der Graph bidirektional ist, z. '{: a [: a: b]: b [: b: a]}' dann würden Sie in einer Endlosschleife stecken bleiben, ohne die besuchten Knoten im Auge zu behalten. – Solaxun
@Solaxun richtig, für Grafiken, die Sie beschreiben, ist es so. Aber für einfache Bäume, wo alle Kinder die Elemente von verschachtelten Sammlungen sind, wie in diesem Fall, macht es einfach keinen Sinn. – leetwinski
Ich hätte in meiner Beschreibung vielleicht expliziter sein können, nehme ich an, aber ich habe diesen Input nie angegeben oder gesagt Baum :) Auch - ist dein erstes Beispiel nicht wirklich ein BFS? Es sieht so aus, als ob du die Kinder 'xs' von links nach rechts verarbeitest. Wie würde das funktionieren, wenn Sie mit einer Diagrammstruktur arbeiten, in die Sie an einem bestimmten Punkt einsteigen, untergeordnete Elemente erstellen und von dort aus fortfahren möchten, anstatt den gesamten Baum sequenziell zu bearbeiten. – Solaxun