Constraints in Kürze
Prof. Dr. W. Conen – zur
Klausurvorbereitung
Januar 2006
Genereller Ablauf der Suche

Gegeben: Variablen X, Domains D,
Constraints R (GENAU explizit oder implizit gegeben)

SOLVE(Assignment A,Freie Variablen X, Constraints C, Domains D)
 Variable x auswählen; x aus X entfernen; Werte sichern
 solange „noch keine konsistente Lösung gefunden“
(auf „frischen“ Kopien A‘,... der gesicherten Werte arbeiten – nur bereits
erfolglos probierte Werte werden zusätzlich aus dem Domain von x entfernt)
Wert v für die Variable auswählen und propagieren,
falls dies möglich ist
 Wenn nicht, „unlösbar“ zurückgeben, sonst
 v aus Dx entfernen; <x,v> zu A‘ hinzufügen
 SOLVE(A‘,X‘,C‘,D‘);
Werte für A,X,C,D aus der letzten Runde übernehmen
„Lösbar“ zurückgeben (Lösung ist in A)



Genereller Ablauf der Suche

Gegeben: Variablen X, Domains D, Constraints R

SOLVE(Assignment A,Freie Variablen X, Constraints C, Domains D)
 if (X == {}) return true;
x à SELECT_VARIABLE(A,X,C,D); X à X – {x};



consistent à false; Ds à D;
while NOT consistent do
 A‘ Ã A; D‘ Ã Ds; C‘ Ã C; X‘ Ã X;
// Neue Arbeitskopien
 v à SELECT_VALUE(x,A‘,X‘,C‘,D‘); // inkl. Propagierung
 if (v == ‚inconsistent‘) return false; else Dsx à Dsx – {v}
 A‘ à A‘ [ <x,v>; consistent à Solve(A‘,X‘,C‘,D‘);
A Ã A‘; X = X‘; C Ã C‘; D = D‘; return true;
Genereller Ablauf der Suche

SELECT_VARIABLE(Freie Variablen X, Constraints C, Domains D)
 first à true;
 foreach x 2 X do
 if ((|Dx| < min) OR first) then
 minvar à x; max à |Dx|; first à false;

Hier kann man natürlich auch kompliziertere Betrachtungen anstellen
zur Variablenauswahl
Wir wählen hier die Variable, die die wenigsten „Restwerte“ im Domain
hat (also am stärksten „constrained“ ist)



Es macht übrigens keinen Sinn, nach einem Scheitern von Solve auf
der darüberliegenden Ebene eine andere Variablenreihenfolge zu
probieren
Anmerkung: X,C,D sind jeweils Mengen (ebenso A auf der vorigen
Folie)
Genereller Ablauf der Suche

SELECT_VALUE(x,A,X,C,D);
// Annahme: in den Domains sind nur Werte, die, einzeln betrachtet, konsistent
zur Teillösung A sind (wegen der letzten Propagierung)





consistent à false; value à ‚inconsistent‘
foreach v 2 Dx do
 A‘ à A [ <x,v>; Dx à Dx – {v}; D‘ à D; C‘ à C
 if PROPAGATE(<x,v>,A‘,X,D‘,C‘) then
 if NOT consistent OR BETTER(X,D‘,C‘,Dc,Cc) then
 Ac à A‘, Dc à D‘; Cc à C‘; value à v; consistent à true;
if consistent A Ã Ac; D Ã Dc; C Ã Cc;
return value; // ‚inconsistent‘ im Inkonsistenzfall
Hier könnte man auch auf das BETTER verzichten und nur
solange auf der zufälligen Reihenfolge der Werte arbeiten,
bis man etwas konsistentes gefunden hat
Genereller Ablauf der Suche


BETTER (X,D‘,C‘,Dc,Cc);
 count_D‘ Ã 0; // Kummulierte Größe der verbleibenden Domainen
 count_Dc à 0;
 foreach x 2 X do
 count_D‘ Ã count_D‘ + |D‘x|;
 count_Dc à count_Dc + |Dcx|;
 if (count_D‘ > count_Dc) then return true else false;
Das ist eine mögliche Bewertung: wieviele Werte verbleiben in den
Domains der noch freien Variablen?
 Vieles anderes (auch mit Gewichtungen der „Wichtigkeit“ von
Werten/Variablen) ist denkbar...
 Wir können dieses hier verwenden, oder auch die Paare zählen, die
in den Constraints verbleiben (sinnvoller bei Pathconsistency)
Genereller Ablauf der Suche

PROPAGATE(<x,v>,A,X,C,D);
// Variante 1: Forward Checking
 foreach y 2 X do // Über jede freie Variable laufen
 foreach vy 2 Dy do
 if Constraint_Verletzt(A [ <y,vy>,C,D) then
 Dy à Dy – {vy}
 If Dy == {} then return false;
 return true;


// 2. Variante: Arc Consistency
// 3. Variante (paßt nicht unmittelbar): Path Consistency
Arc Consistency
Vergleich
FC = Forward Checking+DVO, AC=Arc consistency nach der Wertwahl.
Uns fehlen noch viele weiterführende Details, aber FC+AC ist schon
nicht so schlecht für die aufgeführten Benchmarkprobleme!
Sonst noch: Path Consistency – verändert
Constraints!

PPT