AIMA Notizen

Teil II
Kapitel 5: Constraint Satisfaction Problems (~Probleme bei denen Einschränkungen erfüllt werden müssen)

Inhalt

die Probleme werden nicht mehr als Black-Box gesehen, sondern logisch strukturiert

Menge von Variablen X_i mit Domänen D_i und Menge von Beschränkungen (constraints) C_i.
Zustand des Problems ist die Zuordnung von Werten zu den Variablen
eine Zuordnung, die keine Constraints verletzt heißt konsistent,
eine konsistente Zuordnung, die jeder Variable einen Wert zuordnet ist eine Lösung des Problems
Constraint-Graph: Knoten sind Variablen, Kanten sind Beschränkungen (geht nur für binäre Constraints, für höherstellige Constraints "hypergraphs", wie Petrinetze)
Standardsuchverfahren mit CSPs:

Wurzel: leere Zuordnung, Nachfolgerfunktion: passende Belegung einer unbelegten Variable, Ziel-Test: die Zuordnung ist komplett, Pfad-Kosten: 1 für jeden Schritt

Stelligkeit der Constraints
absolute constraints vs. preference constraints, weighted constraints, die "möglichst" nicht gebrochen werden sollen

in jedem Schritt wird einer Variablen ein Wert zugeordnet, wenn es nicht mehr weitergeht wird rückgesetzt
zunächst nicht besonders effizient
erst problemunabhängige Heuristiken helfen:

Reihenfolge der Belegung von Variablen: welche Variable sollte als nächstes (und wie?) belegt werden?

"fail-first", minimum remaining values (MRV): die Variable mit den wenigsten nach möglichen Werten wird zuerst belegt. So erkennen wir möglichst früh, ob wir auf dem Holzweg sind
"degree heuristic": bei gleich vielen Möglichkeiten wird die Variable belegt, die in den meisten Constraints vorkommt, um den Verzweigungsfaktor möglichst klein zu halten
wir belegen so, dass die übrigen Variablen möglichst wenig eingeschränkt werden

forward-checking: wenn wir eine Variable X belegen, prüfen wir für alle Y die mit X über einen Constraint verbunden sind die zulässigen Werte und löschen alle unzulässigen Werte aus der Domäne von Y.
während forward-checking nur einen Schritt vorausschaut, schaut constraint propagation noch weiter voraus und kann entferntere Sackgassen schon früher vorausahnen

wie kann wiederholtes Backtracking in immer wieder ähnlichen Situationen vermieden werden?

normalerweise wird immer nur der letzte Schritt rückgängig gemacht, auch wenn er garnicht der Grund für das Problem ist (chronologisches Backtracking)
Backtracking wird durch einen Konflikt ausgelöst, die am Konflikt beteiligten Variablen bilden die Konflikt-Menge.
Backjumping: es wird bis zu einer Variable die am Konflikt beteiligt ist zurückgesprungen
Backjumping ist redundant zu forward-checking

eine zufällige an einem Konflikt beteiligte Variable wird gewählt und so neu belegt, dass sie möglichst wenige der Constraints verletzt

lokale Suche ist gut online zu gebrauchen, da ber veränderten Zielen nur wenige Änderungen nötig sind und das neue Ergebnis dem alten sehr nah kommt und nur wenige Veränderungen kommuniziert werden müssen

baumförmige Probleme (jede Kombination von Variablen kommt höchstens in einem Constraint vor) lassen sich in O(nd²) lösen
cutset-conditioning: Probleme lassen sich durch geschicktes Löschen von Knoten in baumförmige Probleme umwandeln (das ist zwar NP-hart, aber es gibt gute Heuristiken)
tree decomposition: Zerteilung des Problems in Teilprobleme, die baumförmig verbunden sind, divide and conquer

letzte Änderung: 20. Dezember 2004.

mail AT timobaumann.de