Strategie bei der Tiefensuche |
Wähle als nächsten zu expandierenden Knoten einen beliebigen unter denen mit maximaler Pfadlänge (Tiefe) aus. |
Und man könnte für die Tiefensuche mit backtracking hinzufügen: ... und stelle das Expandieren der restlichen solange zurück, bis der eben expandierte sich als nicht erfolgreich erwiesen hat. |
Wir untersuchen die o.a. Aussage am Beispielprogramm
einfache schematische Tiefensuche.
Unser Beispiellabyrinth soll die folgende Form haben:
1 | -- | 2 | -- | 3 |
I | I | |||
4 | -- | 5 | 6 | |
I | I | I | ||
7 | 8 | 9 |
Zunächst einmal gehen wir dabei von einem einfachen gerichteten Graphen aus, also einem Baum. Damit wird die Lösbarkeit natürlich abhängig von der Wahl von Startknoten und Zielknoten. Als Startknoten wählen wir den Wurzel - Knoten 1 und als Zielknoten den Knoten 8.
Verfolgen Sie die Schritte der Expansion des Graphen!
In einer an Listen orientierten Sprache wie Scheme passt folgende Datenstruktur zu unserem Problem:
(define Graph '( (1 (2 4)) (2 (3)) (3 (6)) (4 (5 7)) (5 (8)) (6 (9)) (7 ()) (8 ()) (9 ())))
Man bezeichnet sie als Assoziationsliste. Sie setzt sich aus einer Liste von Listen zusammen, die jeweils die Bezeichnung des Knotens enthalten, verbunden mit einer weiteren geschachtelten Liste, welche die Knoten enthält, zu denen man von diesem aus kommen kann.
Eine solche Datenstruktur ist in Scheme so naheliegend, dass es eine Zugriffsfunktion für Assoziationslisten gibt: assoc