I need some hel if possible with the following problem.....The WalkSat algorithm takes a formula, a probability 0 p 1, and a boundary of maximum flips maxflips
and returns a model that satisfies the formula or failure. The algorithm begins by assigning truth values to
the atoms randomly, ie. generating a random model. Then it proceeds to flip the value of an atom from one
of the unsatisfied clauses until it is able to find a model that satisfies the formula or reaches the maximum
number of flips.
In order to select which atom from the currently selected clause to flip, it follows two strategies:
1. Either flip any atom randomly.
2. Or flip the atom that maximizes the number of satisfied clauses in the formula.
The choice to flip randomly is followed with probability p.
1.atomsClause :: Clause ! [Atom] This function must take a Clause and return the set of Atoms of
that Clause. Note that the set should not contain any duplicates.
2. atoms :: Formula![Atom] This function must take a Formula return the set of Atoms of a Formula.
Note that the set should not contain any duplicates.
3. isLiteral :: Literal ! Clause ! Bool This function returns True if the given Literal can be found
within the Clause.
4. flipSymbol :: Model ! Atom ! Model This function must take a Model and an Atom and flip the
truth value of the atom in the model.
Here is the code:
module Algorithm where
import System.Random
import Data.Maybe
import Data.List
type Atom = String
type Literal = (Bool,Atom)
type Clause = [Literal]
type Formula = [Clause]
type Model = [(Atom, Bool)]
type Node = (Formula, ([Atom], Model))
atomsClause :: Clause -> [Atom]
atomsClause = undefined
atoms :: Formula -> [Atom]
atoms = undefined
isLiteral :: Literal -> Clause -> Bool
isLiteral = undefined
flipSymbol :: Model -> Atom -> Model
flipSymbol = undefined
Thank you.
4 replies to this topic
#1
Posted 31 January 2011 - 06:04 AM
|
|
|
#2
Posted 31 January 2011 - 06:06 AM
# probability 0 < p < 1
#3
Posted 31 January 2011 - 06:55 AM
I was thinking for the first one to write it like this......atomsClause :: Clause -> [Atom]
atomsClause [(Bool,Atom)] =[a|(b,a)<-(Bool,Atom)] ...is this ok?
atomsClause [(Bool,Atom)] =[a|(b,a)<-(Bool,Atom)] ...is this ok?
#4
Posted 31 January 2011 - 07:38 AM
ok...I have done the first one....tomsClause xs = nub [a|(b,a)<-xs]....any help with the second one?
#5
Posted 31 January 2011 - 08:51 AM
Ok ,apparently this silence is stimulating me....atoms :: Formula -> [Atom]
atoms = atomsClause.concat
isLiteral :: Literal -> Clause -> Bool
isLiteral (b,a) cs = or[x==b && y==a|(x,y)<-cs]....any help with the last one?
atoms = atomsClause.concat
isLiteral :: Literal -> Clause -> Bool
isLiteral (b,a) cs = or[x==b && y==a|(x,y)<-cs]....any help with the last one?
1 user(s) are reading this topic
0 members, 1 guests, 0 anonymous users


Sign In
Create Account

Back to top









