zurück Programmablauf
;;;                           
(require (lib "breakpoint.ss"))
;;; ===== schematische-Tiefensuche ==================================
;;; Die Tiefensuche ist zunaechst abstrakt definiert. Erst die
;;; jeweilige Implementation der Prozedur Nachfolger und die
;;; Behandlung der Alternativen als Liste haengt von der Art
;;; der Repraesentation des Graphes ab.
;;; Es wird hier davon ausgegangen, dass dieser in einer
;;; Assoziationsliste vorliegt.
;;; Muster :
;;; ( (1.Knoten (1.Nachfolger 2.Nachfolger ...))
;;;   (2.Knoten (1.Nachfolger 2.Nachfolger ...))
;;;    ... )
;;;
;;; Die folgende Variante ermoeglicht nur eine Suche nach der
;;; ersten Loesung. Zyklen werden in dieser Version nicht 
;;; abgefangen. Allerdings gilt dann:
;;; Der Graph muss gerichtet sein, sonst entstehen primitive Zyklen.
;;; ===== Tiefensuche ===============================================
; fuehrt eine Tiefensuche mit backtracking unter Verwendung
; des Systemstacks aus.
; Knoten x Knoten x Assoziationsliste --> boolean
; Die Ausgabe des Weges erfolgt aus der Liste besucht, wenn
; eine Suche erfolgreich war.
; Durch die lokale let-Schleife wird das Übergeben von Start, Ziel
; und Graph vermieden.

(define
  (Tiefensuche Start Ziel Graph)

  (let
    t-s
    ((Alternativen (Nachfolger Start Graph)))

    (cond     ; Erläuterung von cond am Beispiel

      ((null? Alternativen) #f)                      ; [Anm.1]

      ((eq? (car Alternativen) Ziel)                 ; [Anm.3]
       (Ausgabe (car Alternativen))
       (car Alternativen))

      ((t-s                                          ; [Anm.4]:
        (Nachfolger (car Alternativen) Graph))
       (Ausgabe (car Alternativen))
       (car Alternativen))

      (else
       (t-s                                          ; [Anm.5]
        (cdr Alternativen))))))

; [Anm.1]: Wenn auf einer Rekursionstiefe alle Alternativen
;   untersucht wurden, wird mit dem Wert "#f" zur aufrufenden
;   Ebene zurueckgesprungen.
; Anmerkung 2 folgt später !
; [Anm.3]: Wenn das Ziel erreicht wurde, wird der Knoten ausgegeben
;   und zur aufrufenden Ebene zurueckgegeben.
;   Daher wird der Wert dort als "#t" behandelt.

; [Anm.4]: Hier erfolgt der eigentliche Abstieg in der Rekursion.

; [Anm.5]: Wenn die Rekursion in der Tiefe erfolglos war, muss noch
;   die Rekursion in der Breite versucht werden.

;;; ===== Nachfolger ================================================
;;; Die Funktion Nachfolger ist zentral notwendig für die Lösung.
;;; Sie generiert jeweils zu einem Knoten die Liste aller seiner Nachfolger.
(define
   (Nachfolger Element Graph)
   (cadr (assoc Element Graph)))

;;; ===== Ausgabe ===================================================
; Die Hilfsfunktion Ausgabe ermöglicht eine einfache Darstellung des Weges
(define
  (Ausgabe Knoten)
  (display Knoten)
  (display " <-- "))

;;; ===== Graph ==================================================
; globale Variable in der der Graph gespeichert wird.
; Der Graph muss gerichtet sein, sonst entstehen primitive Zyklen.
(define
   Graph
   '( (1 (2 4))
      (2 (3))
      (3 (6))
      (4 (5 7))
      (5 (8))
      (6 (9))
      (7 ())
      (8 ())
      (9 ())))

;;; ===== Labyrinth dazu ============================================
;;; Labyrinth dazu :
;;;                °°°°°°°°°°°
;;;                °1 - 2 - 3°
;;;                °I °°°°° I°
;;;                °4 - 5   6°
;;;                °I ° I ° I°
;;;                °7 ° 8   9°
;;;                °°°°°°°°°°°
;;; ===== Aufruf ====================================================
(define Start 1)
(define Ziel 8)
(if (Tiefensuche Start Ziel Graph) (display Start))