Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
CSPs: “Constraints should be specied formally and precisely.”
In the homework (Problem 4.1) and in the exams from the last few years, in the CSP scheduling problem description always mention that “Constraints should be specied formally and precisely”, yet the solutions provided for this problems do not specify them formally and precisely like in the lecture.
Instead, they are definied like this:
C1 =/= C2
C2 =/= C3
etc.
Does this count as “formally and precisely”? Or should we write them down like in the lecture, i.e. C_C1,C2 ={(A,C)}?
You can give constraints either as formulas or as sets of tuples.
The lecture officially only the latter. But it is straightforward and necessary in practice to allow the former as an efficient representation of the latter.
In the former case, it is already precise from the variables occurring in the formula which constraint it is, e.g., x != y must be the constraint C_{xy}.
In the latter, it is necessary to give the variables, e.g., {(0,1),(1,0)} is not enough, we must say C_{xy}={(0,1),(1,0)}.
So the 50 queens problem for example would just be:
Vi =/= Vj
abs(i-j)=/=abs(Vi-Vj)
Plus the list of variables and their domains.