Nächste Seite: 2.11.3 Begriffsverbände Vorige Seite: 2.11.1 Datenbanken

2.11.2 Bedingungsnetze

Wir haben zu Beginn dieses Abschnitts die Ausdrucksmächtigkeit des jeweiligen Formalismus als unser vorherrschendes Ordnungskriterium erklärt. Der einfachste Formalismus in dieser Hinsicht ist die Termlogik. In ihr betrachten wir logische Probleme der Form (dh. das auftretende Prädikat spielt eine triviale Rolle, die man ignorieren kann) bzw. Varianten hiervon. Das sieht trivialer aus, als es wirklich ist, kann doch ein außerordentlich komplexer Term sein, der ein kompliziertes funktionales (zB. LISP) Programm repräsentiert. Wegen der in Abschnitt 1.3 genannten Wissensrepräsentationshypothese haben wir diesen funktionalen Teil nicht als eigenständigen Formalismus innerhalb unserer Diskussion zugelassen (obwohl er natürlich immer Bestandteil über die auftretenden Terme ist).

Datenbankformalismen sind aus logischer Sicht in etwa von der Form , wobei die Grundatome sind. Anfragen sind Atome, die Variablen enthalten und in der Liste der Grundatome in instantiierter Form auftreten können (in welchem Fall die Instantiierung die Antwort liefert). Bedingungsnetze sind aus syntaktischer Sicht nur geringfügig komplizierter als Datenbanken, indem sie als Anfragen Konjunktionen von Atomen (und nicht nur Atome allein) enthalten können, in denen gemeinsame Variable auftreten können. Diese formulieren gewissermaßen die (Rand-) Bedingungen, unter denen eine Lösung gesucht wird. Trotz dieser scheinbar einfachen Gestalt stellt das Lösen von Bedingungsnetzen bereits ein NP-vollständiges Problem dar.

Bei dem Studium dieses Problemtyps hat sich eine netzartige Darstellung eingebürgert, die in Abbildung 2.36 anhand des in Abbildung 2.35 gezeigten Bedingungsproblems eines Kreuzworträtsels illustriert wird. Die Knoten repräsentieren je eine Variable und ihren Datenbereich, während die Kanten je eine Bedingung zwischen zwei Variablen darstellen. [Ric89] stellt diese Netze allerdings dual dar, dh. die Variablen werden den Kanten und die Knoten den Prädikaten zugeordnet, was ebenfalls möglich, aber ungebräuchlich ist.

Abbildung 2.35: Ein Kreuzworträtsel

Abbildung 2.36: Ein Bedingungsnetz zum Kreuzworträtsel der Abbildung 2.35

Da wir in Abschnitt 1.5.3 gewissermaßen die These aufgestellt haben, daß die Darstellungsform sich aus den durchzuführenden Operationen ergibt, wäre eine diesbezügliche Untersuchung der Bedingungsnetze sehr aufschlußreich, die aber nach Kenntnis des Autors bislang nicht vorliegt. Über die Netze selbst gibt es eine äußerst umfangreiche Literatur, deren Inhalt wir eher zur Deduktion im engeren Sinne rechnen, weshalb wir in diesem Buch nicht ausführlicher darauf eingehen, vielmehr diesbezüglich auf den Abschnitt 4.4.1 in [Bib92] sowie auf den Sonderband [FM92] über ``Constraint-Based Reasoning'' des Artificial Intelligence Journal verweisen wollen.