CSU 670 Fall 2007 Out: October 5, 2007 Due October 12, 2007This subproject consists of 3 parts: Producing Raw Materials, Communication and Coordination and Roadmap.
Input: CNF type T Output: Weighted CNF F of type T in which only a small fraction of the clauses can be satisfied. CNF F contains max_clauses clauses and max_variables variables. Postcondition: Ideally we would like to have an F that minimizes the fraction of clauses that can be satisfied. Can we achieve such a post condition efficiently?
With our lack of information about what the most difficult raw material of a given type T is, let's try something that is easy to implement and maybe a good approximation of what we are looking for. Consider a type T = ((j1,p1) (j2,p2). The js are the clause length and the ps are the number of positive literals. Consider one pair of the type and lets call it (j,p). Let's assume that we have n variables. Let's generate ALL clauses of type (j,p) with n variables. How many are there: choose(n,j)*choose(j,p) where choose(n,k) is the binomial coefficient n choose k.
Example:
n=4, j=2, p=1
choose(n,j)*choose(j,p) = 6 * 2 = 12.
Here they are: (one clause per line)
!1 2
1 !2
!1 3
1 !3
!1 4
1 !4
!2 3
2 !3
!2 4
2 !4
!3 4
3 !4
Given a type T = ((j1,p1) (j2,p2) we generate
choose(n,j1)*choose(j1,p1) clauses for the first pair and
choose(n,j2)*choose(j2,p2) clauses for the second pair.
Those clauses are delivered as raw material.
We don't take advantage of assigning weights to the clauses; currently all clauses have weight 1. In your own algorithmic player you should choose a clever way to assign weights to the clauses to make it harder to satisfy a large fraction of the clauses.
Implement a simple Administrator and Player for the Blackboard Architecture using a black board in a file system F that we have chosen. Implement the following sequence of transactions for one turn of the player: Put all the transactions for one turn as one batch into the blackboard. The Adminstrator tells the player that it is its turn by setting a flag in the blackboard. The Player gets the store. The player prepares a list of transactions and puts them into the blackboard. The Administrator collects it and updates the store etc.