Been working through ther exam scheduling problem. One needs to
upgrade pip and install the constraint module for all the code:
* * *
An example of aconstraint satisfaction problem. Courses A to G need to be
schedules so that no one has two exams at the same time...
Backtracking manually to find one solution:
Doing it with difficult to write code:
doing it with simple code that calls the constraint module:
Voilà, there is more than one solution.
* * *
A simple constraint satisfaction problem:
The nodes represent the exams.There are only edges between them if there
is a constraint, here, same student. Each is called an arc.
As a rule, one looks for node consistency first; that would be whether all courses have
exams, not a problem in this case.
Then one looks for arc consistency: can one remove domains from a variable - here, a
possible exam day - and keep going.
If not, one reports a failiure and backtracks to start again with another variable.
The algorithm as a whole is called AC-3, Arc Consistency -3.
No comments:
Post a Comment