Lab 4 2014

From 6.034 Wiki

(Difference between revisions)
Jump to: navigation, search
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.
-
For review here is roughly a sketch of how these two constraint checking algorithms work.
+
Similarly
-
=== Forward Checking ===
+
Running:
-
# Finds all the constraints that apply to the currently assigned variable.
+
<pre>
-
# For each of the neighbor variables connected by a constraint.
+
python map_coloring_csp.py [dfs|fc|fcps]
-
## Reduce the domain of neighbor variables for values that fail the constraint.
+
</pre>
-
## If the domain of any neighbor variable is reduced down to the empty set, then the check fails.
+
-
=== Forward Checking with Propagation through Singletons ===
+
Should return search trees for the B,Y,R, state coloring problem from the 2006 Quiz 2.
-
# 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
+
-
## Check if constraints with neighbor variables hold (for all values).
+
-
## If not then reduce the neighbor variable's domain
+
-
## Fail if domain of a neighbor is reduced down to the empty set.
+
-
## If new singletons are introduced add them to your queue.
+
-
## Stop when there are no more singletons.
+
== LEARNING ==
== LEARNING ==
-
Now for the fun part.  Learning!   (Not that CSPs were not fun.)
+
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 6.034tas@csail.mit.edu about it.
+
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.


Retrieved from "https://ai6034.mit.edu/wiki/index.php?title=Lab_4_2014"