Backward Chaining

In Prolog (Logik-Prgrammiersprache). Du fragst: grandparent(X, hans). ("Wer ist Opa von Hans?"). Prolog sucht: "Um Opa zu sein, muss man Vater eines Elternteils sein. Suche Eltern von Hans..." Auch beim Debugging: "Warum ist Variable X null? Wo wurde sie gesetzt? Ah, in Zeile 50. Warum war sie da null?"

1. Depth-First Search (DFS)

Meist implementiert als Tiefensuche. Es verfolgt eine Hypothese so tief wie möglich ("Bohren"). Erst wenn es eine Sackgasse findet ("Kein Husten"), geht es zurück (Backprinting) und probiert den nächsten Zweig.

2. Effizienz

Viel effizienter als Forward Chaining, wenn man ein spezifisches Ziel hat. Forward Chaining würde sinnlos tausende Fakten ableiten ("Er hat blaue Augen", "Er trägt Jeans"), die für die Diagnose "Grippe" völlig egal sind.

1. SLD-Resolution (Die Mathematik von Prolog)

In der Logik-Programmierung basiert Backward Chaining auf der SLD-Resolution (Selective Linear Definite Clause Resolution). Das Programm ist eine Menge von Horn-Klauseln (WENN-DANN Aussagen). Der Computer versucht, einen Widerspruchsbeweis (Refutation) zu führen. Er nimmt dein Ziel (Opa(x)) und die Negation an. Dann "resolviert" er diese mit den bekannten Regeln, bis er bei TRUE landet. Dieser Prozess nutzt Unifikation: Das System sucht nach Werten für Variablen (z. B. $X = \text{Karl}$), die den logischen Ausdruck wahr machen. Das ist viel mächtiger als einfaches Pattern Matching, da es Variablen-Bindungen über tiefe Ketten hinweg "durchreicht".

2. Das Problem der Zyklizität & Tabling

Backward Chaining kann in Endlosschleifen hängen bleiben, wenn Regeln zirkulär sind: A :- B. und B :- A. Ein naiver Algorithmus fragt A -> fragt B -> fragt A... und stürzt ab (Stack Overflow). Moderne Systeme (wie XSB Prolog) nutzen Tabling (Memoization). Das System merkt sich: "Ich bin gerade dabei, Ziel A zu lösen." Wenn es erneut bei Ziel A vorbeikommt, wartet es auf das Ergebnis der ersten Anfrage, statt eine neue zu starten. Das verwandelt Backward Chaining von einer einfachen Suche in eine Form von Dynamischer Programmierung.

3. Pruning: Der "Cut" Operator

In der Produktion muss man den Suchbaum klein halten. Ein Backward-Chainer würde sonst Millionen von Wegen probieren, die logisch korrekt, aber sinnlos sind. In Prolog gibt es den Cut-Operator (!). Er sagt dem Algorithmus: "Wenn du bis hierher gekommen bist, ist dies der einzige Weg. Suche nicht weiter in anderen Zweigen, falls ein Fehler passiert." Dies zerstört zwar die rein mathematische Reinheit ("Logische Deklarativität"), ist aber für die Performance von Expertensystemen in Echtzeit-Umgebungen (z.B. Fraud Detection) unerlässlich.