0votos

Bactracking en Haskell

por josejuan hace 4 años

Aunque quizás el problema de partición de conjuntos es el más fácil de los problemas más difíciles en NP, no parece que eso lo haga más fácil de resolver ;P es por tanto, un problema muy difícil de resolver. Para pequeñas instancias, sirve cualquier algoritmo ingenuo (como el que posteo).

backtracking.

1
2
3
4
5
6
7
split xs = snd $ head $ sort [(abs(sum a - sum b), (a, b)) | (a, b) <- back xs, length a `elem` [u, v]] 
           where back [x]    = [([x], [])] 
                 back (x:xs) = concat [[(x:a, b), (a, x:b)] | (a, b) <- back xs] 
                 size        = length xs 
                 (u, v)      = (size `div` 2, size - u) 
 
-- NOTA: para casos en que están acotados |xs| y el dominio de x existen algoritmos eficientes. 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.