PART 3:
=================================================
We implement simple functionality that you need for the project.
All implementation is done in DemeterF because the programs
look like designs and can easily be adapted to other structures.
Use our standard notation:
/home/lieber/.www/courses/csu670/f08/project/project3/rawmat
We use the following example using a short-hand notation
(slightly different than our standard):
CSP-Formula F:
5: 22 1 2 3 // 5 is weight, 22 the relation
4: 22 1 2 4
2: 2 1 2 4
PART A:
===========================================================
Compute the Shannon cofactors of a CSP-formula F for a literal z of variable x.
Given F, we want to compute F_x and F_x'
according to the formula:
F = x and F_x or x' and F_x'
Use Ahmed Abdelmeged's relation class in
http://www.ccs.neu.edu/home/lieber/courses/csg110/sp08/project/project4/IR-2.0/doc/
Source code:
/home/lieber/.www/courses/csg110/sp08/project/project4/IR-2.0
The Shannon cofactors are useful for many algorithms.
Flow based design to be implemented in DemeterF:
Flow through the CSP-formula F and build the cofactor F_x
by reducing each constraint by setting x to true
in each constraint. For example, the constraint
5: 22 1 2 3, where 1 is set to true reduces to
5: ? 2 3
where ? is the relation number returned by Ahmed's Relation class.
Reducing a constraint means to create a new one
with the same weight, a new relation number and possibly one fewer variable.
Computing a Shannon cofactor is a translation from the
language CSP-formula onto itself and therefore calls
for the use of the Bc class.
How do you send the literal z? Use an update method.
You need it when you find the new relation number
on the way back of flowing through a constraint.
And you need it each time you visit a variable.
PART B:
===========================================================
Compute quality(F,J) of assignment J for CSP-formula F.
J = (1,!2,!3,4) // !2 is 2 negated.
quality(F,J) = (5+2/11)=7/11
Flow through the CSP-formula
and use the reduce function from Ahmed's class for each constraint.
Looks like a good use of TUCombiner? The fold is summation.
The leaves are the constraints which reduce to a number.