----------------------------------------------------------------------------- -- | -- Module : Control.Search.Local.Neighbourhood -- Copyright : (c) Richard Senington & David Duke 2010 -- License : GPL-style -- -- Maintainer : Richard Senington <sc06r2s@leeds.ac.uk> -- Stability : provisional -- Portability : portable -- -- Simple Neighbourhood functions for the representation of problems to the library. -- All neighbourhood functions must ultimately be of the form a->[a]. -- -- This module also contains some additional code for the modeling of problems and the -- link between the model and the library. ----------------------------------------------------------------------------- module Control.Search.Local.Neighbourhood ( exchange, basicExchange, NumericallyPriced(priceSolution) ) where import Data.List -- | following helper function pinched from http://www.polyomino.f2s.com/david/haskell/combinatorics.html combinationsOf 0 _ = [[]] combinationsOf _ [] = [] combinationsOf k (x:xs) = map (x:) (combinationsOf (k-1) xs) ++ combinationsOf k xs {- | my code again from here on The first type of neighbourhood is based upon combination exchange in a sequence of elements. This is appropriate for something like TSP, where order matters, but would be less useful for SAT. It takes 2 numbers as parameters, one of which is the number of exchanges to perform, the other the maximum distance within the list. For example exchange 2 2, would change up to 2 elements in each neighbourhood, either adjacent or separated by 1 other element. -} exchange :: Eq a=>Int->Int->[a]->[[a]] exchange _ 0 inlist = [inlist] exchange exchanges dist inlist = nub (map (implement inlist) variants) where len = (length inlist -1) opts = [(x,x+y) | x<-[0..len],y<-[1..dist],x+y<= len] variants = combinationsOf exchanges opts implement :: [a]->[(Int,Int)]->[a] implement i [] = i implement i ((x,y):xs) = implement (begin++[x2]++middle++[x1]++rest') xs where (begin,x1:rest) = splitAt x i (middle,x2:rest') = splitAt (y-x-1) rest -- | We provide the most basic exchange system for testing basicExchange :: Eq a=>[a]->[[a]] basicExchange = exchange 1 1 {- | Some transformations (and the manual inspector of the search process) need to be able to extract a numeric price from a solution. To use these, the solution representation data type must be a part of the following class, please see the example code. -} class (Ord b,Num b)=>NumericallyPriced a b | a->b where priceSolution :: a->b