<br><br><div class="gmail_quote">On Mon, Jan 31, 2011 at 9:11 PM, Manolache Andrei-Ionut <span dir="ltr"><<a href="mailto:andressocrates90@yahoo.com" target="_blank">andressocrates90@yahoo.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<table cellspacing="0" cellpadding="0" border="0"><tbody><tr><td valign="top" style="font:inherit">I need some help if possible with the following problem.....The WalkSat
algorithm takes a formula, a probability 0 =< p =< 1, and a
boundary of maximum flips maxflips
<br>and returns a model that satisfies the formula or failure. The algorithm begins by assigning truth values to
<br>the atoms randomly, ie. generating a random model. Then it proceeds to flip the value of an atom from one
<br>of the unsatisfied clauses until it is able to find a model that satisfies the formula or reaches the maximum
<br>number of flips.
<br>In order to select which atom from the currently selected clause to flip, it follows two strategies:
<br>1. Either flip any atom randomly.
<br>2. Or flip the atom that maximizes the number of satisfied clauses in the formula.
<br>The choice to flip randomly is followed with probability p.
<br>1.atomsClause :: Clause ! [Atom] This function must take a Clause and return the set of Atoms of
<br>that Clause. Note that the set should not contain any duplicates.
<br>2. atoms :: Formula![Atom] This function must take a Formula return the set of Atoms of a Formula.
<br>Note that the set should not contain any duplicates.
<br>3. isLiteral :: Literal ! Clause ! Bool This function returns True if the given Literal can be found
<br>within the Clause.
<br>4. flipSymbol :: Model ! Atom ! Model This function must take a Model and an Atom and flip the
<br>truth value of the atom in the model.
<br><br>Now I've done the first 3 I need some help with the last one, Here is the code:
<br>module Algorithm where
<br><br>import System.Random
<br>import Data.Maybe
<br>import Data.List
<br><br>type Atom = String
<br>type Literal = (Bool,Atom)
<br>type Clause = [Literal]
<br>type Formula = [Clause]
<br>type Model = [(Atom, Bool)]
<br>type Node = (Formula, ([Atom], Model))
<br><br>atomsClause :: Clause -> [Atom]
<br>atomsClause = nub . map snd
<br><br>atoms :: Formula -> [Atom]
<br>atoms =atomsClause . concat
<br><br>isLiteral :: Literal -> Clause -> Bool
<br>isLiteral (b,a) cs = or[x==b && y==a|(x,y)<-cs]
<br><br>flipSymbol :: Model -> Atom -> Model
<br>flipSymbol = undefined
---the last one<br>Thank you.
</td></tr></tbody></table><br><br></blockquote><div><br></div><div>Hi,</div><div><br></div><div>I guess that</div><div><br></div><div>flipSymbol m a = map f m</div><div> where</div><div> f (atom, value) = if a == atom then (atom, not value) else (atom, value)</div>
<div><br></div><div>should do the trick.</div></div><br><div>-- </div><div>Mihai</div>