CSP - Backtracking

Question 1

Wie ist der Pseudoalgorithmus vom Backtracking?

Answer 1

Question 2

Was ist der wesentliche Vorteil des Backtracking-Algorithmus gegenüber der normalen Tiefensuche bei CSPs?

Answer 2

Der Backtracking-Algorithmus prüft während der Suche aktiv die Constraints und verwirft frühzeitig ungültige Teilzuweisungen. Dadurch vermeidet er unnötige Berechnungen und reduziert den Suchraum, während die normale Tiefensuche alle möglichen Zuweisungen prüft, auch wenn sie von Anfang an inkonsistent sind.

Question 3

Was ist das First-Fail-Prinzip?

Answer 3

Das First-Fail-Prinzip ist eine Strategie bei der Lösung von CSPs, die zuerst die Variable auswählt, die am schwierigsten zuzuweisen ist (z. B. mit der kleinsten Domäne). Ziel ist es Konflikte frühzeitig erkennen, um unnötige Berechnungen zu vermeiden und den Suchprozess effizienter zu machen.

Question 4

Was sind typische First-Fail-Heuristiken?

Answer 4

• Belege die Variable mit den meisten Constraints zu den bisher belegten Variablen.
• Belege die Variable mit den meisten starken Constraints zu den bisher belegten Variablen.
• Belege die Variable mit dem kleinsten Wertebereich.

Question 5

Was macht Forward Checking?

Answer 5

Forward Checking überprüft nach jeder Variablenzuweisung, wie sich diese auf die Domänen der noch unbelegten Variablen auswirkt. Falls eine Domäne leer wird (keine gültigen Werte mehr), wird der aktuelle Pfad abgebrochen.

Question 6

Welche Schwächen von Backtracking werden durch Forward Checking minimiert?

Answer 6

1. Spätes Erkennen von Konflikten: Backtracking erkennt Konflikte oft erst nach vollständiger Belegung, während Forward Checking diese frühzeitig erkennt.
2. Unnötige Berechnungen: Backtracking prüft viele inkonsistente Pfade, die Forward Checking frühzeitig ausschließt.
3. Ineffizienz bei großen CSPs: Backtracking durchsucht oft große Teilräume, die Forward Checking durch Domänenreduktion vermeidet.

Question 7

Was ist der Pseudocode für Forward Checking?

Answer 7

Question 8

Wie unterscheiden sich der Zeit- und Speicheraufwand von Forward Checking und Backtracking?

Answer 8

Forward Checking hat einen Quadratischen Rechenaufwand was im Vergleich zum exponentiellen Rechenaufwand für Backtracking billig ist. Der Speicheraufwand ist jedoch erheblich höher.

Question 9

Welche First-Fail-Heuristiken werden häufig bei Constraintpropagierungstechniken verwendet?

Answer 9

1. MRV (Minimum Remaining Values): Wähle die Variable mit der kleinsten Domäne (wenigste verbleibende Werte).
2. Wähle die Variable, die mit den meisten Constraints verbunden ist.

Hinweis: MRV wird häufig in Kombination mit der Gradheuristik als Tiebreaker verwendet.

Question 10

Warum ist Forward Checking bei n-stelligen Constraints mit n>2 wenig effektiv?

Answer 10

Bei n-stelligen Constraints mit n>2:
Es müssen n−1 Variablen belegt sein, bevor das Constraint überprüft werden kann. Dadurch bleibt der Suchbaum auf den ersten n−1 Ebenen breit und hat einen hohen Verzweigungsgrad.

Question 11

Wann funktioniert Forward Checking besonders gut und wann weniger effektiv?

Answer 11

• Besonders gut: Bei restriktiven Constraints, z. B. Gleichheitsconstraints, da diese die Domänen der Variablen stark einschränken.
• Wenig effektiv: Bei schwachen Constraints, z. B. Ungleichheitsconstraints, da diese nur minimale Einschränkungen der Domänen bewirken.