3 ms·
https://en.wikipedia.org/wiki/Constraint_programming https://en.wikipedia.org/wiki/Constraint_programming Basically instead of specifying an algorithm you spec
by pedrocr 13y ago
https://en.wikipedia.org/wiki/Constraint_programming https://en.wikipedia.org/wiki/Constraint_programming
Basically instead of specifying an algorithm you specify the constraints on the variables of the problem and then a generic solving algorithm finds solutions that match your constraints. It's a common solution for some types of problems where it's natural to think in terms of the constraints of the problem. For example to do the schedules for a school with 6 disciplines taught to 7 classes you might think in terms of constraints like:
1) There are 5 classrooms and no room can have 2 classes at once
2) The same discipline can't be taught at the same time to two classes (we only have one professor for each)
3) All classes must have 2h of each discipline
4) Classes must start after 9am and end before 6pm
Instead of designing a data structure and an algorithm to try permutations until you have a working schedule you would define your output variables and then specify these constraints as functions of those variables. In this case the variables would probably be 6*7 tuples of start time and classroom. Then you'd specify the 4 restrictions on those variables. You'd also probably have some kind of optimization function to try and not just get "a" solution but get a good solution (e.g., reduce the number of gaps in the schedule of each class).
Once you've specified both the constraints and the optimization function the generic solving algorithm does the heavy lifting and spits out solutions, sometimes even optimal solutions.