PDF de programación - Tema 23: Técnicas de diseño descendente de algoritmos - Informática (2016–17)

Tema 23: Técnicas de diseño descendente de

algoritmos

Informática (2016–17)

José A. Alonso Jiménez

Grupo de Lógica Computacional

Departamento de Ciencias de la Computación e I.A.

Universidad de Sevilla

IM Tema 23: Técnicas de diseño descendente de algoritmos

Tema 23: Técnicas de diseño descendente de algoritmos
1. La técnica de divide y vencerás

La técnica de divide y vencerás
La ordenación por mezcla como ejemplo de DyV
La ordenación rápida como ejemplo de DyV

2. Búsqueda en espacios de estados

El patrón de búsqueda en espacios de estados
El problema de las n reinas
El problema de la mochila
3. Búsqueda por primero el mejor

El patrón de búsqueda por primero el mejor
El problema del 8 puzzle

4. Búsqueda en escalada

El patrón de búsqueda en escalada
El problema del cambio de monedas por escalada
El algoritmo de Prim del árbol de expansión mínimo por escalada

2 / 52

IM Tema 23: Técnicas de diseño descendente de algoritmos

La técnica de divide y vencerás

La técnica de divide y vencerás

Tema 23: Técnicas de diseño descendente de algoritmos

1. La técnica de divide y vencerás

La técnica de divide y vencerás
La ordenación por mezcla como ejemplo de DyV
La ordenación rápida como ejemplo de DyV

2. Búsqueda en espacios de estados

3. Búsqueda por primero el mejor

4. Búsqueda en escalada

3 / 52

IM Tema 23: Técnicas de diseño descendente de algoritmos

La técnica de divide y vencerás

La técnica de divide y vencerás

La técnica de divide y vencerás
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.

4 / 52

IM Tema 23: Técnicas de diseño descendente de algoritmos

La técnica de divide y vencerás

La técnica de divide y vencerás

La técnica de divide y vencerás

(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 y
pbInicial es el problema inicial.

module DivideVenceras (divideVenceras) where

divideVenceras :: (p -> Bool) -> (p -> s) -> (p -> [p])

divideVenceras ind resuelve divide combina pbInicial =

-> (p -> [s] -> s) -> p -> s

dv' pbInicial where
dv' pb

| ind pb
| otherwise = combina pb [dv' sp | sp <- divide pb]

= resuelve pb

5 / 52

IM Tema 23: Técnicas de diseño descendente de algoritmos

La técnica de divide y vencerás

La técnica de divide y vencerás

La técnica de divide y vencerás

(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 y
pbInicial es el problema inicial.

module DivideVenceras (divideVenceras) where

divideVenceras :: (p -> Bool) -> (p -> s) -> (p -> [p])

divideVenceras ind resuelve divide combina pbInicial =

-> (p -> [s] -> s) -> p -> s

dv' pbInicial where
dv' pb

| ind pb
| otherwise = combina pb [dv' sp | sp <- divide pb]

= resuelve pb

5 / 52

IM Tema 23: Técnicas de diseño descendente de algoritmos

La técnica de divide y vencerás

La ordenación por mezcla como ejemplo de DyV

Tema 23: Técnicas de diseño descendente de algoritmos

1. La técnica de divide y vencerás

La técnica de divide y vencerás
La ordenación por mezcla como ejemplo de DyV
La ordenación rápida como ejemplo de DyV

2. Búsqueda en espacios de estados

3. Búsqueda por primero el mejor

4. Búsqueda en escalada

6 / 52

IM Tema 23: Técnicas de diseño descendente de algoritmos

La técnica de divide y vencerás

La ordenación por mezcla como ejemplo de DyV

La ordenación por mezcla como ejemplo de DyV

(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]

import I1M.DivideVenceras

ordenaPorMezcla :: Ord a => [a] -> [a]
ordenaPorMezcla xs =

divideVenceras ind id divide combina xs
where

ind xs
divide xs

= length xs <= 1
= [take n xs, drop n xs]

combina _ [l1,l2] = mezcla l1 l2

7 / 52

where n = length xs `div` 2

IM Tema 23: Técnicas de diseño descendente de algoritmos

La técnica de divide y vencerás

La ordenación por mezcla como ejemplo de DyV

La ordenación por mezcla como ejemplo de DyV

(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]

import I1M.DivideVenceras

ordenaPorMezcla :: Ord a => [a] -> [a]
ordenaPorMezcla xs =

divideVenceras ind id divide combina xs
where

ind xs
divide xs

= length xs <= 1
= [take n xs, drop n xs]

combina _ [l1,l2] = mezcla l1 l2

7 / 52

where n = length xs `div` 2

IM Tema 23: Técnicas de diseño descendente de algoritmos

La técnica de divide y vencerás

La ordenación por mezcla como ejemplo de DyV

La ordenación por mezcla como ejemplo de DyV

(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)

8 / 52

IM Tema 23: Técnicas de diseño descendente de algoritmos

La técnica de divide y vencerás

La ordenación por mezcla como ejemplo de DyV

La ordenación por mezcla como ejemplo de DyV

(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)

8 / 52

IM Tema 23: Técnicas de diseño descendente de algoritmos

La técnica de divide y vencerás

La ordenación rápida como ejemplo de DyV

Tema 23: Técnicas de diseño descendente de algoritmos

1. La técnica de divide y vencerás

La técnica de divide y vencerás
La ordenación por mezcla como ejemplo de DyV
La ordenación rápida como ejemplo de DyV

2. Búsqueda en espacios de estados

3. Búsqueda por primero el mejor

4. Búsqueda en escalada

9 / 52

IM Tema 23: Técnicas de diseño descendente de algoritmos

La técnica de divide y vencerás

La ordenación rápida como ejemplo de DyV

La ordenación rápida como ejemplo de DyV

(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]

import I1M.DivideVenceras

ordenaRapida :: Ord a => [a] -> [a]
ordenaRapida xs =

divideVenceras ind id divide combina xs
where

ind xs
divide (x:xs)

= length xs <= 1
= [[ y | y <- xs, y <= x],

[ y | y <- xs, y > x]]

combina (x:_) [l1,l2] = l1 ++ [x] ++ l2

10 / 52

IM Tema 23: Técnicas de diseño descendente de algoritmos

La técnica de divide y vencerás

La ordenación rápida como ejemplo de DyV

La ordenación rápida como ejemplo de DyV

(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]

import I1M.DivideVenceras

ordenaRapida :: Ord a => [a] -> [a]
ordenaRapida xs =

divideVenceras ind id divide combina xs
where

ind xs
divide (x:xs)

= length xs <= 1
= [[ y | y <- xs, y <= x],

[ y | y <- xs, y > x]]

combina (x:_) [l1,l2] = l1 ++ [x] ++ l2

10 / 52

IM Tema 23: Técnicas de diseño descendente de algoritmos

Búsqueda en espacios de estados

El patrón de búsqueda en espacios de estados

Tema 23: Técnicas de diseño descendente de algoritmos

1. La técnica de divide y vencerás

2. Búsqueda en espacios de estados

El patrón de búsqueda en espacios de estados
El problema de las n reinas
El problema de la mochila

3. Búsqueda por primero el mejor

4. Búsqueda en escalada

11 / 52

IM Tema 23: Técnicas de diseño descendente de algoritmos

Búsqueda en espacios de estados

El patrón de búsqueda en espacios de estados

Descripción de los problemas de espacios de estados
Las características de los problemas de espacios de estados son:

un conjunto de las posibles situaciones o nodos que constituye el
espacio de estados (estos son las potenciales soluciones que se
necesitan explorar),

un conjunto de movimientos de un nodo a otros nodos, llamados

los sucesores del nodo,

un nodo inicial y
un nodo objetivo que es la solución.

Se supone que el grafo implícito de espacios de estados es acíclico.

12 / 52

IM Tema 23: Técnicas de diseño descendente de algoritmos

Búsqueda en espacios de estados

El patrón de búsqueda en espacios de estados

El patrón de búsqueda en espacios de estados
(buscaEE s o e) es la lista de soluciones del problema de espacio de
estado definido por la función sucesores (s), el objetivo (o) y estado
inicial (e).

module BusquedaEnEspaciosDeEstados (buscaEE) where
import I1M.Pila

buscaEE:: (Eq nodo) => (nodo -> [nodo])

-> (nodo -> Bool)

buscaEE sucesores esFinal x = busca' (apila x vacia)

-> nodo -> [nodo]

where busca' p
| esVacia p
| esFinal (cima p) = cima p : busca' (desapila p)
| otherwise

= busca' (foldr apila (desapila p)

= []

(sucesores x))

where x = cima p

13 / 52

IM Tema 23: Técnicas de diseño descendente de algoritmos

Búsqueda en espacios de esta