<div dir="ltr">I agree that it's a graph traversal model, but IMO you model rooms as nodes, and period changes are edges, with a room change having a cost of 1 and no-change having a cost of 0.<div><br></div><div>I think that given the relatively small number of permutations of teachers in classrooms vs cheap computing power, you could generate the graph entire state space first. Also a second set of weights is recorded with total changes by teacher.</div><div><br></div><div>The "fewest total room changes" is then the minimal spanning tree of the graph.</div><div><br></div><div>If each edge records room changes, by teacher, then the "fewest total room changes" is then the minimal spanning tree of the graph using the sum of the individual teacher-room-changes for weight, and the "lowest average room changes per teacher" is simply computing averages on the second set of states, and then sorting.</div><div><br></div><div>This brings back fond college AI memories of writing lisp to solve one of those 9-tile numbered square puzzles with 8 numbered tiles and one empty space. Good times. </div><div><div><br></div><div><br></div><div><br></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, May 28, 2015 at 4:20 PM, Joe Shaw <span dir="ltr"><<a href="mailto:joe@joeshaw.org" target="_blank">joe@joeshaw.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi,<br><br><div>At first blush this looks a bit like a graph or tree problem to me. The way I would go about modeling this is that each period change would be a node on the tree and would incur a penalty score of some sort. Moving a teacher might incur a penalty of 1, for instance. Maybe that number increases exponentially as the teacher is subsequently moved, in order to satisfy condition #2. Completely disallowed moves would incur a huge penalty (say, 1000 whereas other penalties are in the 1-10 range) like Ms. Anderson being assigned to teach period 6 or Ms. Chastain being moved to other rooms. A score of 0 is the optimal (but maybe impossible) result with this scoring heuristic.</div><div><br></div><div><span style="line-height:1.5;font-size:13.1999998092651px">If you do depth first search you can then completely prune branches of the tree as soon as they incur a penalty greater than the best path seen so far. You could also prune with a breadth first search but then you have to track more state as you go along.</span><br></div><div><span style="line-height:1.5;font-size:13.1999998092651px"><br></span></div><div><span style="line-height:1.5;font-size:13.1999998092651px">Joe</span></div></div><br><div class="gmail_quote"><div><div class="h5"><div dir="ltr">On Thu, May 28, 2015 at 4:05 PM Eric Floehr <<a href="mailto:eric@intellovations.com" target="_blank">eric@intellovations.com</a>> wrote:<br></div></div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div class="h5"><div dir="ltr"><div><div><div><div><div>How would you go about figuring out the best room schedule in Python? This is a real optimization problem my wife's high school department has.<br><br></div>You have three classrooms: R1, R2, R3<br><br></div>The day is segmented into 7 periods. Each classroom can be used all 7 periods, or not.<br><br></div>There are 4 teachers. Each teacher needs to teach class for 5 periods, but they can be any of the 7 periods of the day. Each teacher has one period where they can't teach (listed), and one period where they won't have to teach that can be any period of the day:<br><br></div>Ms. Anderson, can't teach period 6<br>Mr. Boxleitner, can't teach period 2<br>Ms. Chastain, can't teach period 7<br>Mr. Duchovny, can't teach period 3<br><br></div><div>Additionally, Ms. Chastain must teach in the same room for all 5 of her class periods. The other three teachers can move rooms as necessary.<br><br></div><div>What is the "optimal" arrangement of teachers in rooms to meet these constraints? "Optimal" means:<br><br></div><div>1. Fewest room changes, where a room change is defined as a teacher moving from one room to another. For example, if Ms. A seven period schedule is: period 6 and 7 off, and period 1 in room 1, period 2 in room 2, period 3 in room 2, period 4 in room 1 and period 5 in room 2, that is three total room changes.<br><br></div><div>2. Lowest average room changes per teacher. I.e. 3 teachers moving once is preferable to 1 teacher moving 3 times.<br><br></div><div>3. A room change with a break in between is preferable to an immediate room change. A "break" is either the teacher's free period or their "can't teach" period. For example, if Ms. A teaches in room 1 every period except period 7 where she teaches in room 2, that's preferable to teaching period 1 in room 2 and then period 2 (and other periods) in room 1.<br><br></div><div>Beyond that, there is no "right" answer.<br><br></div><div>How do you go about providing "good" solutions in Python?<br><br></div><div><br><br></div></div></div></div>
_______________________________________________<br>
CentralOH mailing list<br>
<a href="mailto:CentralOH@python.org" target="_blank">CentralOH@python.org</a><br>
<a href="https://mail.python.org/mailman/listinfo/centraloh" target="_blank">https://mail.python.org/mailman/listinfo/centraloh</a><br>
</blockquote></div>
<br>_______________________________________________<br>
CentralOH mailing list<br>
<a href="mailto:CentralOH@python.org">CentralOH@python.org</a><br>
<a href="https://mail.python.org/mailman/listinfo/centraloh" target="_blank">https://mail.python.org/mailman/listinfo/centraloh</a><br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div>Len Jaffe - Information Technology Smoke Jumper - <a href="mailto:lenjaffe@jaffesystems.com" target="_blank">lenjaffe@jaffesystems.com</a> </div><div>614-404-4214 <a href="https://www.twitter.com/lenJaffe" target="_blank">@LenJaffe</a> <a href="http://www.lenjaffe.com/" target="_blank">www.lenjaffe.com</a><br></div><div>Host of <a href="http://www.meetup.com/techlifecolumbus/" target="_blank">Code Jam Columbus</a> - <a href="https://www.twitter.com/CodeJamCMH" target="_blank">@CodeJamCMH</a></div><div><div>Curator of <a href="http://www.lenjaffe.com/AdventPlanet/" target="_blank">Advent Planet</a> - An Aggregation of Online Advent Calendars.<div><br></div></div></div></div></div></div></div></div></div>
</div>