;;; einfache schematische-Tiefensuche.scm (define (Tiefensuche Start Ziel Graph) (let t-s ((Alternativen (Nachfolger Start Graph))) (cond ((null? Alternativen) #f) ((eq? (car Alternativen) Ziel) (Ausgabe (car Alternativen)) (car Alternativen)) ((t-s (Nachfolger (car Alternativen) Graph)) (Ausgabe (car Alternativen)) (car Alternativen))
Hier gibt es nun erheblichen Erläuterungsbedarf. Der Aufruf der lokalen Schleife t-s erfolgt hier an der Stelle der Bedingung im cond, er hat also die Bedeutung eines Prädikates! Bei den beiden vorigen Möglichkeiten, die untersucht wurden, hatten wir einmal als Wert #f und im anderen Fall hatte ich angemerkt: "... mit einem von #f verschiedenen Wert ...". Diese Eigenschaft können wir hier nutzen. Wenn wir ggf. auf der unteren Stufe Erfolg hatten, können wir hier nun auch den aktuellen Knoten ausgeben und wiederum das backtracking mit einem von #f verschiedenen Wert, hier dem aktuellen Knoten, fortsetzen. Dieser Aufruf stellt also den eigentlichen Schritt in die Tiefe dar! Und wenn alle diese Fälle nicht gegriffen haben, dann müssen wir weiter bei ...
(else (t-s (cdr Alternativen)))))) ;;; ===== Nachfolger ================================================ (define (Nachfolger Element Graph) (cadr assoc Element Graph))) ;;; ===== Ausgabe =================================================== (define (Ausgabe Knoten) (display Knoten) (display " <-- ")) ;;; ===== Aufruf ==================================================== (define Start 1) (define Ziel 8) (if (Tiefensuche Start Ziel Graph) (display Start))Graph Bild des Labyrinthes