Suppose we have a set of courses C = {C1, C2,...Cn}
to be taught in Winter Quarter. We also have a set of profesors
Profs who teach courses, a set of rooms Rooms that can house courses, and
a set of times Times at which courses can be taught.
Formally define a CSP with variables C and values of the
form (P,R,T) where P is in the set Profs,
R is in the set Rooms, and T is in
the set Times.
Specify each constraint first in English and then more formally
using set notation and any other mathematical notation (e.g.
logic) that makes it simple to express the constraints.
You should have at least 2 unary and 2 binary constraints
that make sense in a university.
Consider the following subgraph isomorphism problem. The binary relation F
has the following pairs: F={(1,3)(1,4)(2,1)(3,2)(4,3)(4,5)}.
The binary relation G has the following pairs:
G={(A,C)(A,D)(B,A)(C,B)(C,F)(D,C)(D,E)(F,E)}. We want to find a subgraph
isomorphism (like on CSP lecture slide 15) from the variables {1,2,3,4,5}
to the values {A,B,C,D,E,F}. The constraint relation R is given by:
R = {(i,v,j,v') | if (i,j) is in F then (v,v') must be in G
and if (j,i) is in F then (v',v) must be in G}
This says that if i and j are connected by an edge in relation F,
v and v' must be connected by the edge (in the appropriate direction) in
relation G.
- First draw the 2 graphs F and G.
- Then show the specified parts of the tree search to
find a consistent labeling using only forward checking and
none of the other heuristics. Do this in the blind order that
has variable 1 at level 1 in the tree, variable 2 at level 2,
and so on all the say down to variable 5 at level 5. At each level,
of the values that are still possible, try them in alphabetical order.
- Start the search at node (1,A). Apply forward checking and show
the whole FTAB for variables 2, 3, 4, and 5. Do the same for the
whole subtree under (1,A). If you find any consistent labelings
mark them with a *.
- Do the same for (1,B).
- For every node (except at level 5, the leaves) that you
process, you will show the assignment at that node and
a forward checking table whose rows are all the unassigned
variables (or future units) and whose columns each represent
a possible value. Use 1's for values that are still OK and
0's for values that are ruled out.
- The subtrees below (1,A) and (1,B) are all you have to do.
You don't need to go any further unless you're curious.
