Lab 4 2014
From 6.034 Wiki
(Difference between revisions)
m |
|||
Line 30: | Line 30: | ||
in <tt>lab4.py</tt>. <tt>state</tt> is an instance of <tt>CSPState</tt> an object that keep track of the current variable assignments and domains. | in <tt>lab4.py</tt>. <tt>state</tt> is an instance of <tt>CSPState</tt> an object that keep track of the current variable assignments and domains. | ||
+ | For review here is roughly a sketch of how these two constraint checking algorithms work. | ||
+ | |||
+ | === Forward Checking === | ||
+ | # Let X be the variable currently being assigned. | ||
+ | # Let x be the value being assigned to X. | ||
+ | # Finds all the binary constraints that X is associated with. | ||
+ | # For each neighbor variable, Y, connected to X by a binary constraint. | ||
+ | ## For each y in Y's domain | ||
+ | ### If constraint fails for X=x and Y=y | ||
+ | #### Remove y from Y's domain | ||
+ | ### If the domain of Y is reduced down to the empty set, then the check fails. | ||
+ | # If all constraints passed declare success | ||
+ | |||
+ | === Forward Checking with Propagation through Singletons === | ||
+ | # Run forward checking, fail if forward checking fails. | ||
+ | # Find variables with domains of size 1. | ||
+ | # Build a queue of singleton variables. | ||
+ | # For each singleton variable in the queue | ||
+ | ## Finds all the binary constraints that singleton X is associated with. | ||
+ | ### For each neighbor variable, Y, connected to X by a binary constraint. | ||
+ | #### For each value of y in Y's domain | ||
+ | ##### If constraint fails for X = (X's singleton value) and Y = y | ||
+ | ###### Remove y from the domain of Y for values | ||
+ | ##### If the domain of Y is reduced down to the empty set, then check fails. | ||
+ | # Check if new singletons are introduced, add them to your queue. | ||
+ | # Stop when there are no more singletons. | ||
+ | |||
+ | === Useful Functions === | ||
+ | Here are some useful functions that you should use to implement the checking algorithms: | ||
+ | |||
+ | <tt>Variable</tt>: representation of a variable in the problem | ||
+ | * <tt>get_name()</tt> - returns the name of this variable. | ||
+ | * <tt>is_assigned()</tt> - returns true if we've made an assignment for this variable. | ||
+ | * <tt>get_domain()</tt> - returns a copy of the current domain of this variable. Use this to iterate over values of Y. | ||
+ | * <tt>reduce_domain(value)</tt> - remove <tt>value</tt> from this variable's domain. | ||
+ | * <tt>domain_size()</tt> - returns the size of this variable's domain | ||
+ | |||
+ | <tt>CSPState</tt>: one of the many possible search states (nodes) in the CSP problem | ||
+ | * <tt>get_current_variable()</tt> - gets the name of the variable being currently assigned. | ||
+ | * <tt>get_constraints_by_name(variable_name)</tt> - retrieves all the BinaryConstraint objects associated with <tt>variable_name</tt>. | ||
+ | * <tt>get_variable_by_name(variable_name)</tt> - retrieves the Variable object associated with <tt>variable_name</tt> | ||
+ | * <tt>get_all_variables()</tt> - gets the list of all Variable objects in this CSP problem. | ||
+ | |||
+ | <tt>BinaryConstraint</tt>: a binary constraint on variable i, j: i -> j. | ||
+ | * <tt>get_variable_i_name()</tt> - name of the i variable | ||
+ | * <tt>get_variable_j_name()</tt> - name of the j variable | ||
+ | * <tt>check(state, value_i=value, value_j=value)</tt> - checks the binary constraint for a given CSP state, with variable i set by value i, and variable j set by value j. Returns false if the constraint fails. | ||
+ | |||
+ | === Testing === | ||
For testing, we have provided <tt>moose_csp.py</tt>, an implementation of the seating problem involving a moose, Palin, McCain, Obama, Biden and You -- in terms of the framework as defined in <tt>csp.py</tt>. | For testing, we have provided <tt>moose_csp.py</tt>, an implementation of the seating problem involving a moose, Palin, McCain, Obama, Biden and You -- in terms of the framework as defined in <tt>csp.py</tt>. | ||
Line 40: | Line 89: | ||
<tt>python moose_csp.py fc</tt> or <tt>python moose_csp.py fcps</tt> should return the correct search trees under forward checking and forward checking with singleton propagation. | <tt>python moose_csp.py fc</tt> or <tt>python moose_csp.py fcps</tt> should return the correct search trees under forward checking and forward checking with singleton propagation. | ||
- | + | Similarly | |
- | + | Running: | |
- | + | <pre> | |
- | + | python map_coloring_csp.py [dfs|fc|fcps] | |
- | + | </pre> | |
- | + | ||
- | + | Should return search trees for the B,Y,R, state coloring problem from the 2006 Quiz 2. | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
== LEARNING == | == LEARNING == | ||
- | Now for | + | Now for something completely different. Learning! |
== Classifying Congress == | == Classifying Congress == | ||
Line 218: | Line 257: | ||
- | If you find what you think is an error in the problem set, tell | + | If you find what you think is an error in the problem set, tell 6034tas@csail.mit.edu about it. |
--> | --> |
Revision as of 19:04, 22 October 2010
This problem set is due Friday, October 29th. If you have questions about it, ask the list 6034tas@csail.mit.edu.