CSP - Konsistenz bewahrende Techniken Flashcards
Was ist der Vorteil von globalen Constraintauswertungen?
Der Vorteil liegt in stärkere Wertebereichsbeschneidung als beim Forward Checking.
Was bedeutet 1-Konsistenz in CSPs?
Eine Constraint Satisfaction Problem (CSP) ist 1-konsistent, wenn:
* Jede einzelne Variable in ihrer Domäne mindestens einen Wert hat, der alle unären Constraints (Constraints, die nur diese Variable betreffen) erfüllt.
Was bedeutet 2-Konsistenz in CSPs?
Ein CSP ist 2-konsistent wenn für alle Paare von Variablen (X, Y), zwischen denen ein Constraint C existiert folgende Bedingungen erfüllt sind:
* Jeder Wert in D_X ist gemäß C konsistent zu mindestens einem Wert in D_Y.
* Jeder Wert in D_Y ist gemäß C konsistent zu mindestens einem Wert in D_X.
Was macht der AC-3-Algorithmus
Er stellt 2-Konsistenz für ein CSP her oder terminiert mit der Information, dass das CSP unlösbar ist.
Wie ist der Pseudocode vom AC-3-Algorithmuses.
Wann ist ein CSP k-konsistent?
Ein CSP ist k-konsistent wenn gilt, dass für jede konsistente Belegung beliebiger k-1 Variablen eine konsistente Belegung für die k. Variable existiert.
ist ein k-konsistentes CSP auch automatisch k-1 konsistent?
Nein
Wann ist ein CSP strikt k-konsistent?
Wenn ein CSP strikt k-konsistent ist, dann ist es auch alle in allen niedrigeren Graden konsistent
Was gilt für ein striktes n-konsistentes CSP mit n Variablen?
Wenn ein CSP strikt n-konsistent ist, ist es auch immer lösbar.
Wie schwer ist es ein CSP auf konsistenz zu überprüfen.
Für 2-konsistenz hat der AC-3 Algorithmus eine Laufzeit von O(n^2 * b^3). Mit effizienteren Algorithmen kriegt man aber auch eine Laufzeit von O(n * b^2) mit Speicheraufwand O(n * b) hin. Für höhere Konsistenzen gibt schon keine effizienten Algorithmen mehr und n-konsistenz ist im allgemeinen so schwer wie das eigentliche CSP-Problem, nämlich NP-vollständig.
