StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>In case anyone comes across a similar problem, here's the solution I went with: </p> <p>I ended up using a <a href="http://en.wikipedia.org/wiki/Backtracking" rel="nofollow">Backtracking Search Algorithm</a> for Constraint Satisfaction Problems. All it does it do a normal backtracking search but checks that all constraints are satisfied as it traverses the tree. Here is the pseudo-code:</p> <pre><code>function BACKTRACKING-SEARCH(csp) returns a solution, or failure return BACKTRACK({ }, csp) function BACKTRACK(assignment, csp) returns a solution, or failure if assignment is complete then return assignment var = SELECT-UNASSIGNED-VARIABLE(csp) for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) do if value is consistent with assignment then add {var = value} to assignment result = BACKTRACK(assignment, csp) if result != failure then return result remove {var = value} return failure </code></pre> <p>The variable is a time slot. The possible values assigned to a variable are the workers. The combination of a variable and its actual assignment is a node in the tree. Thus the search space is all the possible combinations of time slots and workers. The constraints prune nodes from the search space. </p> <p>A constraint can be a workers availability. So if time slot A is assigned Worker X, but X is not able to work in time slot A, then this node will be ruled inconsistent. </p> <p>I solved the problem of a particular time slot being assigned multiple workers by considering each time slot / worker combination to be it's OWN time slot. So if the childrens' nursery has 2 workers to fill, I consider it as two individual time slots to fill, each getting assigned its own worker. That way each variable is assigned just one value. It makes for MUCH simpler algorithms.</p> <p>Thanks for all the help whittling this down to a solvable problem.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload