classroom constraint satisfaction problem
Carl Banks
pavlovevidence at gmail.com
Mon Oct 16 01:04:49 CEST 2006
Steven Bethard wrote:
> I'm trying to solve a constraint-satisfaction problem, and I'm having
> some troubles framing my problem in such a way that it can be
> efficiently solved.
>
> Basically, I want to build groups of two teachers and four students such
> that [1]:
>
> * Students are assigned to exactly one group
> * Teachers are assigned to approximately the same number of groups
> * Students are not in groups with their homeroom teachers
> * Students in each group are from four different homerooms
>
> So given teachers A, B, C, D, E and F and their corresponding students
> A1, A2, ... F3, F4, here's a good grouping:
>
> A, B: C1, D1, E1, F1
> B, C: A1, D2, E2, F2
> C, D: A2, B1, E3, F3
> D, E: A3, B2, C2, F4
> E, F: A4, B3, C3, D3
> F, A: B4, C4, D4, E4
[snip]
> [1] There are actually two other constraints that I omitted:
>
> * Some teachers cannot be placed in the same group, e.g. I might know
> that A cannot work with B or that E cannot work with F.
>
> * If you create a graph out of the teacher pairs from all the groups,
> the graph should not be disconnected. That is, the following grouping
> is bad because the teachers are disconnected:
I would do it in two steps.
Step 1: Generate a graph of all teachers, such that there is one
connection for every four students, and each teacher has approximately
equal number of connections. A simple, approximate way to do this
would be to generate random subsets of two teachers until you have
enough connections (though that won't work well if you have a lot of
teachers that can't work together, which wouldn't be surprising). I'm
sure graph theory has some algorithms to do this if you need more
exactitude.
Step 2: Assign students from appropriate homerooms to each connection.
The following simple algorithm is probably satisfactory: for each
connection between teachers, choose a random subset of four homerooms
not governed by those teachers to form a group. Assign a random
student from each homeroom. Once every student from a homeroom has
been been assigned, remove that homeroom from the set of available
homerooms. With this method, you might have some connections at the
end without enough remaining homerooms; just go fishing for a suitable
switch among students already assigned. Or, work out a way to make
sure you don't exhaust too many homerooms. Perhaps there is a known
algorithm for doing this.
Carl Banks
More information about the Python-list
mailing list