I1M2015: El patrón de divide y vencerás en Haskell
En la primera parte de la clase de hoy del curso de Informática de 1º del Grado en Matemáticas hemos estudiado la técnica de resolución de problemas mediante divide y vencerás.
La clase comenzó analizando los árboles de ordenación de una lista de números mediante la ordenación por mezcla y la ordenación rápida.
De este análisis se extrae el patrón de resolución de problemas mediante divide y vencerás (DyV) y sus argumentos:
- cómo reconocer si el problema es elemental,
- cómo se resuelven los problemas elementales,
- cómo se descompone un problema y
- cómo se combinan las soluciones de los subproblemas.
A continuación se implementa el patrón DyV en Haskell, usando su posibilidad de programar en orden superior para abstraer los argumentos del problema.
Finalmente, se aplica el patrón DyV para implementar los algoritmos de ordenación por mezcla y ordenación rápida.
Las transparencias usadas en la clase son las páginas 1-10 del tema 23:
El código del patrón divide y vencerás es
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
module DivideVenceras (divideVenceras) where -- La técnica "divide y vencerás" consta de los siguientes pasos: -- 1. Dividir el problema en subproblemas menores. -- 2. Resolver por separado cada uno de los subproblemas; si los -- subproblemas son complejos, usar la misma técnica recursivamente; -- si son simples, resolverlos directamente. -- 3. Combinar todas las soluciones de los subproblemas en una solución -- simple. -- (divideVenceras ind resuelve divide combina pbInicial) resuelve el -- problema pbInicial mediante la técnica de divide y vencerás, donde -- * (ind pb) se verifica si el problema pb es indivisible -- * (resuelve pb) es la solución del problema indivisible pb -- * (divide pb) es la lista de subproblemas de pb -- * (combina pb ss) es la combinación de las soluciones ss de los -- subproblemas del problema pb. -- * pbInicial es el problema inicial divideVenceras :: (p -> Bool) -> (p -> s) -> (p -> [p]) -> (p -> [s] -> s) -> p -> s divideVenceras ind resuelve divide combina pbInicial = dv' pbInicial where dv' pb | ind pb = resuelve pb | otherwise = combina pb [dv' sp | sp <- divide pb] |
El código de la ordenación por mezcla (mergesort) mediante divide y vencerás es
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
import I1M.DivideVenceras -- (ordenaPorMezcla xs) es la lista obtenida ordenando xs por el -- procedimiento de ordenación por mezcla. Por ejemplo, -- ghci> ordenaPorMezcla [3,1,4,1,5,9,2,8] -- [1,1,2,3,4,5,8,9] ordenaPorMezcla :: Ord a => [a] -> [a] ordenaPorMezcla xs = divideVenceras ind id divide combina xs where ind xs = length xs <= 1 divide xs = [take n xs, drop n xs] where n = length xs `div` 2 combina _ [l1,l2] = mezcla l1 l2 -- (mezcla xs ys) es la lista obtenida mezclando xs e ys. Por ejemplo, -- mezcla [1,3] [2,4,6] == [1,2,3,4,6] mezcla :: Ord a => [a] -> [a] -> [a] mezcla [] b = b mezcla a [] = a mezcla a@(x:xs) b@(y:ys) | x <= y = x : (mezcla xs b) | otherwise = y : (mezcla a ys) |
El código de la ordenación rápida (quicksort) mediante divide y vencerás es
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
import I1M.DivideVenceras -- (ordenaRapida xs) es la lista obtenida ordenando xs por el -- procedimiento de ordenación rápida. Por ejemplo, -- ghci> ordenaRapida [3,1,4,1,5,9,2,8] -- [1,1,2,3,4,5,8,9] ordenaRapida :: Ord a => [a] -> [a] ordenaRapida xs = divideVenceras ind id divide combina xs where ind xs = length xs <= 1 divide (x:xs) = [[ y | y<-xs, y<=x], [ y | y<-xs, y>x] ] combina (x:_) [l1,l2] = l1 ++ [x] ++ l2 |