CSP - Einleitung Flashcards
Was ist ein Constraint Satisfaction Problem (CSP) informal?
Ein Constraint Satisfaction Problem (CSP) ist ein Problem, bei dem Variablen Werte zugewiesen werden sollen, sodass vorgegebene Einschränkungen (Constraints) erfüllt werden.
- Variablen: Werte, die gesucht werden (z. B. x,y,z).
- Domäne: Wertebereich jeder Variable (z. B. x∈{1,2,3}).
- Constraints: Regeln, die die erlaubten Kombinationen festlegen (z. B. 𝑥≠𝑦).
Was ist ein Constrain Satisfaction Problem formal?
Was ist ein binäres Constraint Satisfaction Problem (CSP)?
Ein binäres Constraint Satisfaction Problem (CSP) ist eine spezielle Form eines CSP, bei dem alle Constraints nur höhstens zwei Variablen betreffen.
Was ist eine Belegung bei einem CSP?
Eine Belegung ist die Zuweisung von Werten aus D_i an eine Menge von Variablen X_i. Im Startzustand sind alle Variablen unbelegt (leere Belegung). {A = 2, B = 1} ist ebenfalls eine Belegung.
Was ist eine konsistente Belegung bei einem CSP?
Eine konsistente Belegung ist eine Belegung, die keine Constraints verletzt.
Was ist eine vollständige Belegung bei einem CSP?
Eine vollständige Belegung ist eine Belegung aller Variablen X_i mit Werten aus D_i.
Was ist eien vollständige konsistente Belegung bei einem CSP?
Eine vollständige konsistente Belegung ist eine Lösung für das CSP. Man ermittelt sie
durch Suche.
Warum gelten Variablen mit einstelligem Wertebereich nicht als belegt?
Ein Wertebereich mit nur einem möglichen Wert erfüllt nicht automatisch die Constraints. Die Zuweisung muss geprüft werden, da sie trotz Einstelligkeit inkonsistent sein kann (z. B. 𝑥≠𝑦 ,x=y=1).
