Wie sucht Prolog mit Backtracking?
Backtracking ist die Suchmethode von Prolog. Es probiert eine Möglichkeit, und führt sie nicht zum Ziel, geht es einen Schritt zurück und probiert die nächste.
So findet es zum Beispiel alle Wege von Hamburg nach Berlin in einem Streckennetz, ohne dass Sie die Suche Schritt für Schritt vorschreiben.
Am Ende dieser Lektion
Notiz
Ich kann erklären, wie Prolog bei einer Liste Alternativen ausprobiert und zurückgeht.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Liste | eine Folge von Werten in eckigen Klammern | [anna, ben] |
| Kopf und Rest | das erste Element einer Liste und die übrigen | [K|R] |
| Backtracking | zurückgehen und die nächste Möglichkeit probieren | |
| Wahlpunkt | eine Stelle, an der mehrere Möglichkeiten offen sind | |
| Teilziel | eine der Bedingungen im Rumpf einer Regel |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Eine Liste hat einen Kopf und einen Rest
Eine Liste steht in eckigen Klammern: [anna, ben, carla]. Die leere Liste ist [].
Mit [K|R] trennen Sie eine Liste in Kopf und Rest: K ist das erste Element, R die Liste der übrigen. Aus [anna, ben, carla] wird K gleich anna und R gleich [ben, carla]. Fast jede Regel über Listen benutzt diese Zerlegung.
Eine Liste in Kopf und Rest teilen
docker exec prolog swipl -q -g "[K|R] = [anna, ben, carla], write(K), nl, write(R), nl" -t haltHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Die Listenregeln des Labs ansehen
docker exec prolog cat lists.plHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Eine Regel über Listen benutzen
docker exec prolog swipl -q -g "total([1, 2, 3], S), write(S), nl" -t halt lists.plHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Bei einem Fehlschlag geht Prolog zurück
Passt ein Teilziel nicht, wirft Prolog die letzte Wahl weg und probiert die nächste. Das ist Backtracking. Stellen mit mehreren offenen Möglichkeiten heißen Wahlpunkte.
Beispiel: member(X, [1, 2, 3]) liefert erst 1. Folgt die Bedingung X > 1, scheitert die 1. Prolog geht zurück zum Wahlpunkt und versucht die 2.
Beispiel: member(X, [1, 2, 3]), X > 1
| Schritt | Was Prolog tut | Ausgang |
|---|---|---|
| 1 | X wird 1 (erste Wahl) | Wahlpunkt bleibt offen |
| 2 | Prüft 1 > 1 | Scheitert, zurück |
| 3 | X wird 2 (nächste Wahl) | Wahlpunkt bleibt offen |
| 4 | Prüft 2 > 1 | Gelingt, Antwort: X ist 2 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Die erste Zahl, die passt
docker exec prolog swipl -q -g "member(X, [1, 2, 3, 4]), X * X > 5, write(X), nl" -t haltHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Zurückgehen erzwingen mit fail
docker exec prolog swipl -q -g "member(Z, [a, b]), write(Z), nl, fail ; writeln(ende)" -t haltHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Alle Zerlegungen einer Liste
docker exec prolog swipl -q -g "forall(append(A, B, [1, 2]), (write(A-B), nl))" -t haltHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein häufiger Fehler
Warnung
Viele glauben, Prolog rate zufällig. Es probiert streng der Reihe nach: Fakten von oben nach unten, Teilziele von links nach rechts. Darum ändert die Reihenfolge der Fakten die Reihenfolge der Antworten, aber nicht, welche Antworten es gibt.
Alle Wege durch ein Netz finden
Ein Streckennetz ist eine Menge von Fakten strecke(von, nach). Ein Weg ist eine Liste von Orten. Zwei Regeln beschreiben ihn.
Basisfall: Gibt es eine Strecke direkt, ist [von, nach] ein Weg. Schritt: Von von zu einem Nachbarn Z und von dort weiter. Backtracking liefert jeden Weg einzeln.
Die zwei Wegregeln
% Beispiel: ein Weg ist eine Liste von Orten.
weg(Von, Nach, [Von, Nach]) :- strecke(Von, Nach).
weg(Von, Nach, [Von|Rest]) :-
strecke(Von, Z),
weg(Z, Nach, Rest).Alle Wege von Hamburg nach Berlin
docker exec prolog swipl -q -g "forall(member(A-B, [hamburg-hannover, hannover-berlin, hamburg-berlin]), assertz(strecke(A, B))), assertz((weg(X, Y, [X, Y]) :- strecke(X, Y))), assertz((weg(X, Y, [X|R]) :- strecke(X, Z), weg(Z, Y, R))), forall(weg(hamburg, berlin, W), (write(W), nl))" -t haltHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Das Suchen selbst nachbauen
In Python bauen Sie dieselbe Suche mit einer Funktion nach, die sich selbst aufruft. Die Strecken sind eine Liste von Paaren, Start zuerst. Sie merken sich die schon besuchten Orte, denn sonst läuft die Suche in einem Kreis ewig.
Die Funktion probiert jeden Nachbarn nacheinander aus. Das ist Backtracking als Schleife mit Rekursion.