[Haskell-cafe] Haskell WalkSat algorithm implementation

[Manolache Andrei-Ionut]

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

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.


Now I've done the first 3 I need some help with the last one, 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 = nub . map snd


atoms :: Formula -> [Atom]

atoms =atomsClause . concat


isLiteral :: Literal -> Clause -> Bool

isLiteral (b,a) cs = or[x==b && y==a|(x,y)<-cs]


flipSymbol :: Model -> Atom -> Model

flipSymbol = undefined
---the last one
Thank you.
		
		
	
					


      
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110131/5b240384/attachment.htm>