Steven Bethard a écrit : > 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 > > > My current solution is to create a constraint satisfaction problem using > python-constraint (http://labix.org/python-constraint) where there are
Last time I looked at it, it seemed to not use (by default) its Arc8 routine that prunes domains between each variable instantiation by the backtracker. Did you enable it ? (it should have a crucial performance impact). You could also try the logilab constraint package (http://www.logilab.org/projects/constraint) and see how it fares with your problem (it 'only' provides the AC3 domain pruning algorithm but at least uses it by default). Cheers, Aurélien. > variables for: > > * each student domain: group names > * each group name domain: all pairs of teachers > > This works for simple problems, but because most of my constraints have > to iterate over all students and/or all groups, this takes way too long > on my real dataset (which has 300+ students). I thought about trying to > reframe the problem so that there are variables for: > > * each group name domain: pairs of teachers X 4-tuples of students > > but that seems like it would be generating something like 15^2*300^4 > items for the domain, which is clearly also going to be way too big. > > > Any suggestions on how to speed things up? I've posted my current code_ > and the tests_ in case anyone has the time to look at them. > > .. _code: http://ucsu.colorado.edu/~bethard/py/constraint/student_groups.py > .. _tests: > http://ucsu.colorado.edu/~bethard/py/constraint/test_student_groups.py > > > Thanks! > > Steve > > > [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: > > A, B: ... > C, D: ... > A, B: ... > > while this grouping would be okay: > > A, B: ... > B, C: ... > C, D: ... -- http://mail.python.org/mailman/listinfo/python-list
