La semana en Exercitium (8 de julio de 2023)
Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. El problema de las n reinas (mediante búsqueda por anchura en espacios de estados)
- 2. El problema de la mochila (mediante espacio de estados)
- 3. El tipo abstracto de datos de las colas de prioridad
- 4. Búsqueda por primero el mejor
- 5. El problema del 8 puzzle
A continuación se muestran las soluciones.
1. El problema de las n reinas (mediante búsqueda por anchura en espacios de estados)
El problema de las n reinas consiste en colocar n reinas en un tablero cuadrado de dimensiones n por n de forma que no se encuentren más de una en la misma línea: horizontal, vertical o diagonal.
Las posiciones de las reinas en el tablero se representan por su columna y su fila.
1 2 |
type Columna = Int type Fila = Int |
Una solución del problema de las n reinas es una lista de posiciones.
1 |
type SolNR = [(Columna,Fila)] |
Usando el procedimiento de búsqueda en anchura, definir las funciones
1 2 3 |
solucionesNR :: Columna -> [SolNR] primeraSolucionNR :: Columna -> SolNR nSolucionesNR :: Columna -> Int |
tales que
solucionesNR n
es la lista de las soluciones del problema de las n reinas, por búsqueda de espacio de estados en anchura. Por ejemplo,
1 2 3 4 |
take 3 (solucionesNR 8) [[(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)], [(1,8),(2,3),(3,1),(4,6),(5,2),(6,5),(7,7),(8,4)], [(1,8),(2,2),(3,5),(4,3),(5,1),(6,7),(7,4),(8,6)]] |
primeraSolucionNR n
es la primera solución del problema de las n reinas, por búsqueda en espacio de estados por anchura. Por ejemplo,
1 2 |
λ> primeraSolucionNR 8 [(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)] |
nSolucionesNR n
es el número de soluciones del problema de las n reinas, por búsqueda en espacio de estados. Por ejemplo,
1 |
nSolucionesNR 8 == 92 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
module BEE_Reinas_Anchura where import BusquedaEnAnchura (buscaAnchura) import Test.Hspec (Spec, hspec, it, shouldBe) type Columna = Int type Fila = Int type SolNR = [(Columna,Fila)] -- Los nodos del problema de las n reinas son ternas formadas por la -- columna de la última reina colocada, el número de columnas del -- tablero y la solución parcial de las reinas colocadas anteriormente. type NodoNR = (Columna,Columna,SolNR) solucionesNR :: Columna -> [SolNR] solucionesNR n = map estado (buscaAnchura sucesoresNR esFinalNR (1,n,[])) where estado (_,_,e) = e primeraSolucionNR :: Columna -> SolNR primeraSolucionNR = head . solucionesNR nSolucionesNR :: Columna -> Int nSolucionesNR = length . solucionesNR -- (valida sp p) se verifica si la posición p es válida respecto de la -- solución parcial sp; es decir, la reina en la posición p no amenaza a -- ninguna de las reinas de la sp (se supone que están en distintas -- columnas). Por ejemplo, -- valida [(1,1)] (2,2) == False -- valida [(1,1)] (2,3) == True valida :: SolNR -> (Columna,Fila) -> Bool valida solp (c,r) = and [test s | s <- solp] where test (c',r') = c'+r'/=c+r && c'-r'/=c-r && r'/=r -- (sucesoresNR e) es la lista de los sucesores del estado e en el -- problema de las n reinas. Por ejemplo, -- λ> sucesoresNR (1,4,[]) -- [(2,4,[(1,1)]),(2,4,[(1,2)]),(2,4,[(1,3)]),(2,4,[(1,4)])] sucesoresNR :: NodoNR -> [NodoNR] sucesoresNR (c,n,solp) = [(c+1,n,solp ++ [(c,r)]) | r <- [1..n] , valida solp (c,r)] -- (esFinalNR e) se verifica si e es un estado final del problema de las -- n reinas. esFinalNR :: NodoNR -> Bool esFinalNR (c,n,_) = c > n -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ take 3 (solucionesNR 8) `shouldBe` [[(1,8),(2,4),(3,1),(4,3),(5,6),(6,2),(7,7),(8,5)], [(1,8),(2,3),(3,1),(4,6),(5,2),(6,5),(7,7),(8,4)], [(1,8),(2,2),(3,5),(4,3),(5,1),(6,7),(7,4),(8,6)]] it "e2" $ nSolucionesNR 8 `shouldBe` 92 -- La verificación es -- λ> verifica -- -- e1 -- e2 -- -- Finished in 0.2116 seconds -- 2 examples, 0 failures |
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
from src.BusquedaEnAnchura import buscaAnchura Columna = int Fila = int SolNR = list[tuple[Columna, Fila]] # Los nodos del problema de las n reinas son ternas formadas por la # columna de la última reina colocada, el número de columnas del # tablero y la solución parcial de las reinas colocadas anteriormente. NodoNR = tuple[Columna, Columna, SolNR] # valida(sp, p) se verifica si la posición p es válida respecto de la # solución parcial sp; es decir, la reina en la posición p no amenaza a # ninguna de las reinas de la sp (se supone que están en distintas # columnas). Por ejemplo, # valida([(1,1)], (2,2)) == False # valida([(1,1)], (2,3)) == True def valida(sp: SolNR, p: tuple[Columna, Fila]) -> bool: c, r = p def test(s: tuple[Columna, Fila]) -> bool: c1, r1 = s return c1 + r1 != c + r and c1 - r1 != c - r and r1 != r return all(test(s) for s in sp) # sucesoresNR(e) es la lista de los sucesores del estado e en el # problema de las n reinas. Por ejemplo, # >>> sucesoresNR((1,4,[])) # [(2,4,[(1,1)]),(2,4,[(1,2)]),(2,4,[(1,3)]),(2,4,[(1,4)])] def sucesoresNR (nd: NodoNR) -> list[NodoNR]: c,n,solp = nd return [(c+1,n,solp + [(c,r)]) for r in range(1, n+1) if valida(solp, (c,r))] # esFinalNR(e) se verifica si e es un estado final del problema de las # n reinas. def esFinalNR(nd: NodoNR) -> bool: c, n, _ = nd return c > n def solucionesNR(n: int) -> list[SolNR]: nInicial: NodoNR = (1,n,[]) return [e for (_, _, e) in buscaAnchura(sucesoresNR, esFinalNR, nInicial)] def primeraSolucionNR(n: int) -> SolNR: return solucionesNR(n)[0] def nSolucionesNR(n: int) -> int: return len(solucionesNR(n)) # Verificación # ============ def test_nReinas() -> None: assert solucionesNR(5)[:3] == \ [[(1,1),(2,3),(3,5),(4,2),(5,4)], [(1,1),(2,4),(3,2),(4,5),(5,3)], [(1,2),(2,4),(3,1),(4,3),(5,5)]] assert nSolucionesNR(5) == 10 print("Verificado") # La verificación es # >>> test_nReinas() # Verificado |
2. El problema de la mochila (mediante espacio de estados)
Se tiene una mochila de capacidad de peso p y una lista de n para colocar en la mochila. Cada objeto i tiene un peso w(i) y un valor v(i). Considerando la posibilidad de colocar el mismo objeto varias veces en la mochila, el problema consiste en determinar la forma de colocar los objetos en la mochila sin sobrepasar la capacidad de la mochila colocando el máximo valor posible.
Para solucionar el problema se definen los siguientes tipos:
- Una solución del problema de la mochila es una lista de objetos.
1 |
type SolMoch = [Objeto] |
- Los objetos son pares formado por un peso y un valor
1 |
type Objeto = (Peso,Valor) |
- Los pesos son número enteros
1 |
type Peso = Int |
- Los valores son números reales.
1 |
type Valor = Float |
- Los estados del problema de la mochila son 5-tupla de la (v,p,l,o,s) donde v es el valor de los objetos colocados, p es el peso de los objetos colocados, l es el límite de la capacidad de la mochila, o es la lista de los objetos colocados (ordenados de forma creciente según sus pesos) y s es la solución parcial.
1 |
type NodoMoch = (Valor,Peso,Peso,[Objeto],SolMoch) |
Usando el procedimiento de búsqueda en profundidad, definir la función
1 |
mochila :: [Objeto] -> Peso -> (SolMoch,Valor) |
tal que mochila os l
es la solución del problema de la mochila para la lista de objetos os
y el límite de capacidad l
. Por ejemplo,
1 2 3 4 5 6 7 8 |
> mochila [(2,3),(3,5),(4,6),(5,10)] 8 ([(5,10.0),(3,5.0)],15.0) > mochila [(2,3),(3,5),(5,6)] 10 ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0) > mochila [(8,15),(15,10),(3,6),(6,13),(2,4),(4,8),(5,6),(7,7)] 35 ([(6,13.0),(6,13.0),(6,13.0),(6,13.0),(6,13.0),(3,6.0),(2,4.0)],75.0) > mochila [(2,2.8),(3,4.4),(5,6.1)] 10 ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4) |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
module BEE_Mochila where import BusquedaEnProfundidad (buscaProfundidad) import Data.List (sort) import Test.Hspec (Spec, hspec, it, shouldBe) type Peso = Int type Valor = Float type Objeto = (Peso,Valor) type SolMoch = [Objeto] type NodoMoch = (Valor,Peso,Peso,[Objeto],SolMoch) mochila :: [Objeto] -> Peso -> (SolMoch,Valor) mochila os l = (sol,v) where (v,_,_,_,sol) = maximum (buscaProfundidad sucesoresMoch esObjetivoMoch (inicial os l)) -- (inicial os l) es el estado inicial del problema de la mochila -- para la lista de objetos os y el límite de capacidad l inicial :: [Objeto] -> Peso -> NodoMoch inicial os l = (0,0,l,sort os,[]) -- (sucesoresMoch e) es la lista de los sucesores del estado e en el -- problema de la mochila para la lista de objetos os y el límite de -- capacidad l. sucesoresMoch :: NodoMoch -> [NodoMoch] sucesoresMoch (v,p,l,os,solp) = [( v+v', p+p', l, [o | o@(p'',_) <- os, p''>=p'], (p',v'):solp ) | (p',v') <- os, p+p' <= l] -- (esObjetivoMoch e) se verifica si e es un estado final el problema de -- la mochila para la lista de objetos os y el límite de capacidad l . esObjetivoMoch :: NodoMoch -> Bool esObjetivoMoch (_,p,l,(p',_):_,_) = p+p'>l -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ mochila [(2,3),(3,5),(4,6),(5,10)] 8 `shouldBe` ([(5,10.0),(3,5.0)],15.0) it "e2" $ mochila [(2,3),(3,5),(5,6)] 10 `shouldBe` ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0) it "e3" $ mochila [(8,15),(15,10),(3,6),(6,13),(2,4),(4,8),(5,6),(7,7)] 35 `shouldBe` ([(6,13.0),(6,13.0),(6,13.0),(6,13.0),(6,13.0),(3,6.0),(2,4.0)],75.0) it "e4" $ mochila [(2,2.8),(3,4.4),(5,6.1)] 10 `shouldBe` ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4) -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- -- Finished in 0.0424 seconds -- 4 examples, 0 failures |
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
from src.BusquedaEnProfundidad import buscaProfundidad Peso = int Valor = float Objeto = tuple[Peso, Valor] SolMoch = list[Objeto] NodoMoch = tuple[Valor, Peso, Peso, list[Objeto], SolMoch] # inicial(os, l) es el estado inicial del problema de la mochila # para la lista de objetos os y el límite de capacidad l def inicial(os: list[Objeto], l: Peso) -> NodoMoch: return (0,0,l,sorted(os),[]) # sucesoresMoch(e) es la lista de los sucesores del estado e en el # problema de la mochila para la lista de objetos os y el límite de # capacidad l. def sucesoresMoch(n: NodoMoch) -> list[NodoMoch]: (v,p,l,os,solp) = n return [( v+v1, p+p1, l, [(p2,v2) for (p2,v2) in os if p2 >= p1], [(p1,v1)] + solp ) for (p1,v1) in os if p + p1 <= l] # esObjetivoMoch(e) se verifica si e es un estado final el problema de # la mochila para la lista de objetos os y el límite de capacidad l . def esObjetivoMoch(e: NodoMoch) -> bool: (_, p, l, os, _) = e (p_, _) = os[0] return p + p_ > l def mochila(os: list[Objeto], l: Peso) -> tuple[SolMoch, Valor]: (v,_,_,_,sol) = max(buscaProfundidad(sucesoresMoch, esObjetivoMoch, inicial(os, l))) return (sol, v) # Verificación # ============ def test_Mochila() -> None: assert mochila([(2,3),(3,5),(4,6),(5,10)], 8) == \ ([(5,10.0),(3,5.0)],15.0) assert mochila([(2,3),(3,5),(5,6)], 10) == \ ([(3,5.0),(3,5.0),(2,3.0),(2,3.0)],16.0) assert mochila([(2,2.8),(3,4.4),(5,6.1)], 10) == \ ([(3,4.4),(3,4.4),(2,2.8),(2,2.8)],14.4) print("Verificado") # La verificación es # >>> test_Mochila() # Verificado |
3. El tipo abstracto de datos de las colas de prioridad
1. El tipo abstracto de datos de las colas de prioridad
Una cola de prioridad es una cola en la que cada elemento tiene asociada una prioridad. La operación de extracción siempre elige el elemento de menor prioridad.
Las operaciones que definen a tipo abstracto de datos (TAD) de las colas de prioridad (cuyos elementos son del tipo a) son las siguientes:
1 2 3 4 5 |
vacia :: Ord a => CPrioridad a inserta :: Ord a => a -> CPrioridad a -> CPrioridad a primero :: Ord a => CPrioridad a -> a resto :: Ord a => CPrioridad a -> CPrioridad a esVacia :: Ord a => CPrioridad a -> Bool |
tales que
- vacia es la cola de prioridad vacía.
- (inserta x c) añade el elemento x a la cola de prioridad c.
- (primero c) es el primer elemento de la cola de prioridad c.
- (resto c) es el resto de la cola de prioridad c.
- (esVacia c) se verifica si la cola de prioridad c es vacía.
Las operaciones tienen que verificar las siguientes propiedades:
- inserta x (inserta y c) == inserta y (inserta x c)
- primero (inserta x vacia) == x
- Si x <= y, entonces primero (inserta y (inserta x c)) == primero (inserta x c)
- resto (inserta x vacia) == vacia
- Si x <= y, entonces resto (inserta y (inserta x c)) == inserta y (resto (inserta x c))
- esVacia vacia
- not (esVacia (inserta x c))
2. Las colas de prioridad en Haskell
2.1. El tipo abstracto de datos de las colas de prioridad en Haskell
El TAD de las colas de prioridadd se encuentra en el módulo ColaDePrioridad.hs cuyo contenido es el siguiente:
1 2 3 4 5 6 7 8 9 10 |
module TAD.ColaDePrioridad (CPrioridad, vacia, -- Ord a => CPrioridad a inserta, -- Ord a => a -> CPrioridad a -> CPrioridad a primero, -- Ord a => CPrioridad a -> a resto, -- Ord a => CPrioridad a -> CPrioridad a esVacia, -- Ord a => CPrioridad a -> Bool ) where import TAD.ColaDePrioridadConListas |
Para usar el TAD hay que usar una implementación concreta. En principio,
solo considearemos una que usa las listas.
2.2. Implementación de las colas de prioridad mediante listas
La implementación se encuentra en el módulo ColaDePrioridadConListas.hs cuyo contenido es el siguiente:
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 |
{-# LANGUAGE FlexibleInstances #-} {-# OPTIONS_GHC -fno-warn-unused-top-binds #-} module TAD.ColaDePrioridadConListas (CPrioridad, vacia, -- Ord a => CPrioridad a inserta, -- Ord a => a -> CPrioridad a -> CPrioridad a primero, -- Ord a => CPrioridad a -> a resto, -- Ord a => CPrioridad a -> CPrioridad a esVacia, -- Ord a => CPrioridad a -> Bool ) where import Test.QuickCheck -- Colas de prioridad mediante listas. newtype CPrioridad a = CP [a] deriving Eq -- (escribeColaDePrioridad c) es la cadena correspondiente a la cola de -- prioridad c. Por ejemplo, -- λ> escribeColaDePrioridad (inserta 5 (inserta 2 (inserta 3 vacia))) -- "2 | 3 | 5" escribeColaDePrioridad :: Show a => CPrioridad a -> String escribeColaDePrioridad (CP []) = "-" escribeColaDePrioridad (CP [x]) = show x escribeColaDePrioridad (CP (x:xs)) = show x ++ " | " ++ escribeColaDePrioridad (CP xs) -- Procedimiento de escritura de colas de prioridad. instance Show a => Show (CPrioridad a) where show = escribeColaDePrioridad -- Ejemplo de cola de prioridad -- λ> inserta 5 (inserta 2 (inserta 3 vacia)) -- 2 | 3 | 5 -- vacia es la cola de prioridad vacía. Por ejemplo, -- λ> vacia -- CP [] vacia :: Ord a => CPrioridad a vacia = CP [] -- (inserta x c) es la cola obtenida añadiendo el elemento x a la cola -- de prioridad c. Por ejemplo, -- λ> inserta 5 (foldr inserta vacia [3,1,7,2,9]) -- 1 | 2 | 3 | 5 | 7 | 9 inserta :: Ord a => a -> CPrioridad a -> CPrioridad a inserta x (CP q) = CP (ins x q) where ins y [] = [y] ins y r@(e:r') | y < e = y:r | otherwise = e:ins y r' -- (primero c) es el primer elemento de la cola de prioridad c. Por -- ejemplo, -- primero (foldr inserta vacia [3,1,7,2,9]) == 1 primero :: Ord a => CPrioridad a -> a primero (CP(x:_)) = x primero _ = error "primero: cola de prioridad vacia" -- (resto c) es la cola de prioridad obtenida eliminando el primer -- elemento de la cola de prioridad c. Por ejemplo, -- λ> resto (foldr inserta vacia [3,1,7,2,9]) -- 2 | 3 | 7 | 9 resto :: Ord a => CPrioridad a -> CPrioridad a resto (CP (_:xs)) = CP xs resto _ = error "resto: cola de prioridad vacia" -- (esVacia c) se verifica si la cola de prioridad c es vacía. Por -- ejemplo, -- esVacia (foldr inserta vacia [3,1,7,2,9]) == False -- esVacia vacia == True esVacia :: Ord a => CPrioridad a -> Bool esVacia (CP xs) = null xs -- Generador de colas de prioridad -- =============================== -- genCPrioridad es un generador de colas de enteros. Por ejemplo, -- λ> sample genCPrioridad -- - -- 0 | 0 -- 4 -- -4 | -3 | 6 | 6 -- -7 | -6 | -2 | 0 -- -10 | -10 | -5 | 1 | 4 | 6 | 6 | 9 | 10 -- - -- -13 | -11 | -9 | -5 | -2 | -1 | 0 | 1 | 2 | 2 | 13 | 14 -- -15 | -13 | -13 | -5 | -3 | -1 | 3 | 5 | 7 | 9 | 9 | 14 | 16 -- - -- -17 | -15 | -14 | -5 | -2 | 1 | 1 | 2 | 5 | 7 genCPrioridad :: (Arbitrary a, Num a, Ord a) => Gen (CPrioridad a) genCPrioridad = do xs <- listOf arbitrary return (foldr inserta vacia xs) -- El tipo cola de prioridad es una instancia del arbitrario. instance (Arbitrary a, Num a, Ord a) => Arbitrary (CPrioridad a) where arbitrary = genCPrioridad -- Propiedades de las colas de prioridad -- ===================================== -- Propiedad. Si se añade dos elementos a una cola de prioridad se -- obtiene la misma cola de prioridad idependientemente del orden en -- que se añadan los elementos. prop_inserta_conmuta :: Int -> Int -> CPrioridad Int -> Bool prop_inserta_conmuta x y c = inserta x (inserta y c) == inserta y (inserta x c) -- Comprobación. -- λ> quickCheck prop_inserta_conmuta -- +++ OK, passed 100 tests. -- Propiedad. La cabeza de la cola de prioridad obtenida añadiendo un -- elemento x a la cola de prioridad vacía es x. prop_primero_inserta_vacia :: Int -> CPrioridad Int -> Bool prop_primero_inserta_vacia x _ = primero (inserta x vacia) == x -- Comprobación. -- λ> quickCheck prop_primero_inserta_vacia -- +++ OK, passed 100 tests. -- Propiedad. El primer elemento de una cola de prioridad c no cambia -- cuando se le añade un elemento mayor o igual que algún elemento de c. prop_primero_inserta :: Int -> Int -> CPrioridad Int -> Property prop_primero_inserta x y c = x <= y ==> primero (inserta y c') == primero c' where c' = inserta x c -- Comprobación. -- λ> quickCheck prop_primero_inserta -- +++ OK, passed 100 tests. -- Propiedad. El resto de añadir un elemento a la cola de prioridad -- vacía es la cola vacía. prop_resto_inserta_vacia :: Int -> Bool prop_resto_inserta_vacia x = resto (inserta x vacia) == vacia -- Comprobación. -- λ> quickCheck prop_resto_inserta_vacia -- +++ OK, passed 100 tests. -- Propiedad. El resto de la cola de prioridad obtenida añadiendo un -- elemento y a una cola c' (que tiene algún elemento menor o igual que -- y) es la cola que se obtiene añadiendo y al resto de c'. prop_resto_inserta :: Int -> Int -> CPrioridad Int -> Property prop_resto_inserta x y c = x <= y ==> resto (inserta y c') == inserta y (resto c') where c' = inserta x c -- Comprobación: -- λ> quickCheck prop_resto_inserta -- +++ OK, passed 100 tests. -- Propiedad. vacia es una cola vacía. prop_vacia_es_vacia :: Bool prop_vacia_es_vacia = esVacia (vacia :: CPrioridad Int) -- Comprobación. -- λ> quickCheck prop_vacia_es_vacia -- +++ OK, passed 100 tests. -- Propiedad. Si se añade un elemento a una cola de prioridad se obtiene -- una cola no vacía. prop_inserta_no_es_vacia :: Int -> CPrioridad Int -> Bool prop_inserta_no_es_vacia x c = not (esVacia (inserta x c)) -- Comprobación. -- λ> quickCheck prop_inserta_no_es_vacia -- +++ OK, passed 100 tests. |
3. Las colas de prioridad en Python
3.1. El tipo abstracto de las colas de prioridad en Python
La implementación se encuentra en el módulo ColaDePrioridad.py cuyo contenido es el siguiente:
1 2 3 4 5 6 7 8 9 10 11 |
__all__ = [ 'CPrioridad', 'vacia', 'inserta', 'primero', 'resto', 'esVacia', ] from src.TAD.ColaDePrioridadConListas import (CPrioridad, esVacia, inserta, primero, resto, vacia) |
Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos solo una que usa las listas.
3.2. Implementación de las colas de prioridad mediante listas
La implementación se encuentra en el módulo ColaDePrioridadConListas.py en el que se define la clase CPrioridad con los siguientes métodos:
- inserta(x) añade x a la cola.
- primero() es el primero de la cola.
- resto() elimina el primero de la cola.
- esVacia() se verifica si la cola es vacía.
Por ejemplo,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
>>> c = CPrioridad() >>> c - >>> c.inserta(5) >>> c.inserta(2) >>> c.inserta(3) >>> c.inserta(4) >>> c 2 | 3 | 4 | 5 >>> c.primero() 2 >>> c.resto() >>> c 3 | 4 | 5 >>> c.esVacia() False >>> c = CPrioridad() >>> c.esVacia() True |
Además se definen las correspondientes funciones. Por ejemplo,
1 2 3 4 5 6 7 8 9 10 11 12 |
>>> vacia() - >>> inserta(4, inserta(3, inserta(2, inserta(5, vacia())))) 2 | 3 | 4 | 5 >>> primero (inserta(4, inserta(3, inserta(2, inserta(5, vacia()))))) 2 >>> resto (inserta(4, inserta(3, inserta(2, inserta(5, vacia()))))) 3 | 4 | 5 >>> esVacia(inserta(4, inserta(3, inserta(2, inserta(5, vacia()))))) False >>> esVacia(vacia()) True |
Finalmente, se define un generador aleatorio de colas de prioridad y se comprueba que las colas de prioridad cumplen las propiedades de su especificación.
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 |
from __future__ import annotations __all__ = [ 'CPrioridad', 'vacia', 'inserta', 'primero', 'resto', 'esVacia', ] from abc import abstractmethod from copy import deepcopy from dataclasses import dataclass, field from typing import Generic, Protocol, TypeVar from hypothesis import assume, given from hypothesis import strategies as st class Comparable(Protocol): @abstractmethod def __lt__(self: A, otro: A) -> bool: pass A = TypeVar('A', bound=Comparable) # Clase de las colas de prioridad mediante listas # =============================================== @dataclass class CPrioridad(Generic[A]): _elementos: list[A] = field(default_factory=list) def __repr__(self) -> str: """ Devuelve una cadena con los elementos de la cola separados por " | ". Si la cola está vacía, devuelve "-". """ if not self._elementos: return '-' return ' | '.join(str(x) for x in self._elementos) def esVacia(self) -> bool: """ Comprueba si la cola está vacía. Devuelve True si la cola está vacía, False en caso contrario. """ return not self._elementos def inserta(self, x: A) -> None: """ Inserta el elemento x en la cola de prioridad. """ self._elementos.append(x) self._elementos.sort() def primero(self) -> A: """ Devuelve el primer elemento de la cola. """ return self._elementos[0] def resto(self) -> None: """ Elimina el primer elemento de la cola """ self._elementos.pop(0) # Funciones del tipo de las listas # ================================ def vacia() -> CPrioridad[A]: """ Crea y devuelve una cola vacía de tipo A. """ c: CPrioridad[A] = CPrioridad() return c def inserta(x: A, c: CPrioridad[A]) -> CPrioridad[A]: """ Inserta un elemento x en la cola c y devuelve una nueva cola con el elemento insertado. """ _aux = deepcopy(c) _aux.inserta(x) return _aux def esVacia(c: CPrioridad[A]) -> bool: """ Devuelve True si la cola está vacía, False si no lo está. """ return c.esVacia() def primero(c: CPrioridad[A]) -> A: """ Devuelve el primer elemento de la cola c. """ return c.primero() def resto(c: CPrioridad[A]) -> CPrioridad[A]: """ Elimina el primer elemento de la cola c y devuelve una copia de la cola resultante. """ _aux = deepcopy(c) _aux.resto() return _aux # Generador de colas de prioridad # =============================== def colaAleatoria() -> st.SearchStrategy[CPrioridad[int]]: """ Genera una estrategia de búsqueda para generar colas de enteros de forma aleatoria. Utiliza la librería Hypothesis para generar una lista de enteros y luego se convierte en una instancia de la clase cola. """ return st.lists(st.integers()).map(CPrioridad) # Comprobación de las propiedades de las colas # ============================================ # Las propiedades son @given(c=colaAleatoria(), x=st.integers(), y=st.integers()) def test_cola1(c: CPrioridad[int], x: int, y: int) -> None: assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c)) assert primero(inserta(x, vacia())) == x assert resto(inserta(x, vacia())) == vacia() assert esVacia(vacia()) assert not esVacia(inserta(x, c)) @given(c=colaAleatoria(), x=st.integers(), y=st.integers()) def test_cola2(c: CPrioridad[int], x: int, y: int) -> None: assume(not y < x) assert primero(inserta(y, (inserta(x, c)))) == \ primero(inserta(x,c)) assert resto(inserta(y, (inserta(x, c)))) == \ inserta(y, resto(inserta(x, c))) # La comprobación es # > poetry run pytest -q ColaDePrioridadConListas.py # 2 passed in 0.54s |
4. Búsqueda por primero el mejor
En la búsqueda por primero el mejor se supone que los estados están ordenados mediante una función, la heurística, que es una estimación de su coste para llegar a un estado final.
Definir la función
1 |
buscaPM :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n] |
tal que buscaPM 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
, obtenidas buscando por primero el mejor.
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 |
module BusquedaPrimeroElMejor (buscaPM) where import TAD.ColaDePrioridad (esVacia, inserta, primero, resto, vacia) buscaPM :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n] buscaPM sucesores esFinal x = busca' (inserta x vacia) where busca' c | esVacia c = [] | esFinal (primero c) = primero c : busca' (resto c) | otherwise = busca' (foldr inserta (resto c) (sucesores (primero c))) |
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 |
from __future__ import annotations from abc import abstractmethod from functools import reduce from typing import Callable, Optional, Protocol, TypeVar from src.TAD.ColaDePrioridad import (CPrioridad, esVacia, inserta, primero, resto, vacia) class Comparable(Protocol): @abstractmethod def __lt__(self: A, otro: A) -> bool: pass A = TypeVar('A', bound=Comparable) def buscaPM(sucesores: Callable[[A], list[A]], esFinal: Callable[[A], bool], inicial: A) -> Optional[A]: c: CPrioridad[A] = inserta(inicial, vacia()) while not esVacia(c): if esFinal(primero(c)): return primero(c) es = sucesores(primero(c)) c = reduce(lambda x, y: inserta(y, x), es, resto(c)) return None |
5. El problema del 8 puzzle
Para el 8-puzzle se usa un cajón cuadrado en el que hay situados bloques cuadrados. El cuadrado restante está sin rellenar. Cada bloque tiene un número. Un bloque adyacente al hueco puede deslizarse hacia él. El juego consiste en transformar la posición inicial en la posición final mediante el deslizamiento de los bloques. En particular, consideramos el estado inicial y final siguientes:
1 2 3 4 5 6 7 8 |
+---+---+---+ +---+---+---+ | | 1 | 3 | | 1 | 2 | 3 | +---+---+---+ +---+---+---+ | 8 | 2 | 4 | | 8 | | 4 | +---+---+---+ +---+---+---+ | 7 | 5 | 5 | | 7 | 6 | 5 | +---+---+---+ +---+---+---+ Estado inicial Estado final |
Para solucionar el problema se definen los siguientes tipos:
Tablero
es una matriz de número enteros (que representan las piezas en
cada posición y el 0 representa el hueco):
1 |
type Tablero = Matrix Int |
Estado
es una listas de tableros [t_n,…,t_1] tal que t_i es un
sucesor de t_(i-1).
1 2 |
newtype Estado = Est [Tablero] deriving Show |
Usando el procedimiento de búsqueda por primero el mejor, definir la función
1 |
solucion_8puzzle :: Tablero -> [Tablero] |
tal que (solucion_8puzzle t)
es la solución del problema del problema del 8 puzzle a partir del tablero t
. Por ejemplo,
1 2 3 4 5 6 7 8 |
λ> solucion_8puzzle (fromLists [[0,1,3],[8,2,4],[7,6,5]]) [┌ ┐ ┌ ┐ ┌ ┐ │ 0 1 3 │ │ 1 0 3 │ │ 1 2 3 │ │ 8 2 4 │ │ 8 2 4 │ │ 8 0 4 │ │ 7 6 5 │ │ 7 6 5 │ │ 7 6 5 │ └ ┘, └ ┘, └ ┘] λ> length (solucion_8puzzle (fromLists [[2,6,3],[5,0,4],[1,7,8]])) 21 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 |
module BPM_8Puzzle where import BusquedaPrimeroElMejor (buscaPM) import Data.Matrix (Matrix, (!), fromLists, setElem, toLists) import Test.Hspec (Spec, hspec, it, shouldBe) type Tablero = Matrix Int newtype Estado = Est [Tablero] deriving (Eq, Show) solucion_8puzzle :: Tablero -> [Tablero] solucion_8puzzle t = reverse ts where (Est ts) = head (buscaPM sucesores esFinal (inicial t)) -- Estado inicial -- ============== -- (inicial t) es el estado inicial del problema del 8 puzzle a partir del -- tablero t. inicial :: Tablero -> Estado inicial t = Est [t] -- Estado final -- ============ -- (esFinal e) se verifica si e es un estado final. esFinal :: Estado -> Bool esFinal (Est (n:_)) = n == tableroFinal -- tableroFinal es el estado tablero final del 8 puzzle. tableroFinal :: Tablero tableroFinal = fromLists [[1,2,3], [8,0,4], [7,6,5]] -- Sucesores -- ========= -- (sucesores e) es la lista de sucesores del estado e. Por ejemplo, -- λ> sucesores (Est [fromLists [[2,1,3],[8,0,4],[7,6,5]]]) -- [Est [┌ ┐ ┌ ┐ -- │ 2 0 3 │ │ 2 1 3 │ -- │ 8 1 4 │ │ 8 0 4 │ -- │ 7 6 5 │ │ 7 6 5 │ -- └ ┘, └ ┘], -- Est [┌ ┐ ┌ ┐ -- │ 2 1 3 │ │ 2 1 3 │ -- │ 8 6 4 │ │ 8 0 4 │ -- │ 7 0 5 │ │ 7 6 5 │ -- └ ┘, └ ┘], -- Est [┌ ┐ ┌ ┐ -- │ 2 1 3 │ │ 2 1 3 │ -- │ 0 8 4 │ │ 8 0 4 │ -- │ 7 6 5 │ │ 7 6 5 │ -- └ ┘, └ ┘], -- Est [┌ ┐ ┌ ┐ -- │ 2 1 3 │ │ 2 1 3 │ -- │ 8 4 0 │ │ 8 0 4 │ -- │ 7 6 5 │ │ 7 6 5 │ -- └ ┘, └ ┘]] sucesores :: Estado -> [Estado] sucesores (Est e@(t:_)) = [Est (t':e) | t' <- tablerosSucesores t, t' `notElem` e] -- (tablerosSucesores t) es la lista de los tableros sucesores del -- tablero t. Por ejemplo, -- λ> tablerosSucesores (fromLists [[2,1,3],[8,0,4],[7,6,5]]) -- [┌ ┐ ┌ ┐ ┌ ┐ ┌ ┐ -- │ 2 0 3 │ │ 2 1 3 │ │ 2 1 3 │ │ 2 1 3 │ -- │ 8 1 4 │ │ 8 6 4 │ │ 0 8 4 │ │ 8 4 0 │ -- │ 7 6 5 │ │ 7 0 5 │ │ 7 6 5 │ │ 7 6 5 │ -- └ ┘, └ ┘, └ ┘, └ ┘] tablerosSucesores :: Tablero -> [Tablero] tablerosSucesores t = [intercambia t p q | q <- posicionesVecinas p] where p = posicionHueco t -- Una posición es un par de enteros. type Posicion = (Int,Int) -- (posicionesVecinas p) son las posiciones de la matriz cuadrada de -- dimensión 3 que se encuentran encima, abajo, a la izquierda y a la -- derecha de los posición p. Por ejemplo, -- λ> posicionesVecinas (2,2) -- [(1,2),(3,2),(2,1),(2,3)] -- λ> posicionesVecinas (1,2) -- [(2,2),(1,1),(1,3)] -- λ> posicionesVecinas (1,1) -- [(2,1),(1,2)] posicionesVecinas :: Posicion -> [Posicion] posicionesVecinas (i,j) = [(i-1,j) | i > 1] ++ [(i+1,j) | i < 3] ++ [(i,j-1) | j > 1] ++ [(i,j+1) | j < 3] -- (posicionHueco t) es la posición del hueco en el tablero t. Por -- ejemplo, -- λ> posicionHueco (fromLists [[2,1,3],[8,0,4],[7,6,5]]) -- (2,2) posicionHueco :: Tablero -> Posicion posicionHueco t = posicionElemento t 0 -- (posicionElemento t a) es la posición de elemento a en el tablero -- t. Por ejemplo, -- λ> posicionElemento (fromLists [[2,1,3],[8,0,4],[7,6,5]]) 4 -- (2,3) posicionElemento :: Tablero -> Int -> Posicion posicionElemento t a = head [(i,j) | i <- [1..3], j <- [1..3], t ! (i,j) == a] -- (intercambia t p1 p2) es el tablero obtenido intercambiando en t los -- elementos que se encuentran en las posiciones p1 y p2. Por ejemplo, -- λ> intercambia (fromLists [[2,1,3],[8,0,4],[7,6,5]]) (1,2) (2,2) -- ┌ ┐ -- │ 2 0 3 │ -- │ 8 1 4 │ -- │ 7 6 5 │ -- └ ┘ intercambia :: Tablero -> Posicion -> Posicion -> Tablero intercambia t p1 p2 = setElem a2 p1 (setElem a1 p2 t) where a1 = t ! p1 a2 = t ! p2 -- Heurística -- ========== -- (heuristica t) es la suma de la distancia Manhatan desde la posición de -- cada objeto del tablero a su posición en el tablero final. Por -- ejemplo, -- λ> heuristica (fromLists [[0,1,3],[8,2,4],[7,6,5]]) -- 4 heuristica :: Tablero -> Int heuristica t = sum [distancia (posicionElemento t i) (posicionElemento tableroFinal i) | i <- [0..8]] -- (distancia p1 p2) es la distancia Manhatan entre las posiciones p1 y -- p2. Por ejemplo, -- distancia (2,7) (4,1) == 8 distancia :: Posicion -> Posicion -> Int distancia (x1,y1) (x2,y2) = abs (x1-x2) + abs (y1-y2) -- Comparación de estados -- ====================== -- Un estado es menor o igual que otro si tiene la heurística de su -- primer tablero es menor o que la del segundo o so iguales y el -- primero es más corto. instance Ord Estado where Est (t1:ts1) <= Est (t2:ts2) = (heuristica t1 < heuristica t2) || ((heuristica t1 == heuristica t2) && (length ts1 <= length ts2)) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ map toLists (solucion_8puzzle (fromLists [[0,1,3],[8,2,4],[7,6,5]])) `shouldBe` [[[0,1,3], [8,2,4], [7,6,5]], [[1,0,3], [8,2,4], [7,6,5]], [[1,2,3], [8,0,4], [7,6,5]]] it "e2" $ length (solucion_8puzzle (fromLists [[2,6,3],[5,0,4],[1,7,8]])) `shouldBe` 21 -- La verificación es -- λ> verifica -- -- e1 -- e2 -- -- Finished in 0.1361 seconds -- 2 examples, 0 failures |
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 |
from copy import deepcopy from typing import Optional from src.BusquedaPrimeroElMejor import buscaPM Tablero = list[list[int]] # Tablero final # ============= # tableroFinal es el tablero final del 8 puzzle. tableroFinal: Tablero = [[1,2,3], [8,0,4], [7,6,5]] # Posiciones # ========== # Una posición es un par de enteros. Posicion = tuple[int,int] # Heurística # ========== # distancia(p1, p2) es la distancia Manhatan entre las posiciones p1 y # p2. Por ejemplo, # >>> distancia((2,7), (4,1)) # 8 def distancia(p1: Posicion, p2: Posicion) -> int: (x1, y1) = p1 (x2, y2) = p2 return abs(x1-x2) + abs (y1-y2) # posicionElemento(t, a) es la posición de elemento a en el tablero # t. Por ejemplo, # λ> posicionElemento([[2,1,3],[8,0,4],[7,6,5]], 4) # (1, 2) def posicionElemento(t: Tablero, a: int) -> Posicion: for i in range(0, 3): for j in range(0, 3): if t[i][j] == a: return (i, j) return (4, 4) # posicionHueco(t) es la posición del hueco en el tablero t. Por # ejemplo, # >>> posicionHueco([[2,1,3],[8,0,4],[7,6,5]]) # (1, 1) def posicionHueco(t: Tablero) -> Posicion: return posicionElemento(t, 0) # heuristica(t) es la suma de la distancia Manhatan desde la posición de # cada objeto del tablero a su posición en el tablero final. Por # ejemplo, # >>> heuristica([[0,1,3],[8,2,4],[7,6,5]]) # 4 def heuristica(t: Tablero) -> int: return sum((distancia(posicionElemento(t, i), posicionElemento(tableroFinal, i)) for i in range(0, 10))) # Estados # ======= # Un estado es una tupla (h, n, ts), donde ts es una listas de tableros # [t_n,...,t_1] tal que t_i es un sucesor de t_(i-1) y h es la # heurística de t_n. Estado = tuple[int, int, list[Tablero]] # Estado inicial # ============== # inicial(t) es el estado inicial del problema del 8 puzzle a partir del # tablero t. def inicial(t: Tablero) -> Estado: return (heuristica(t), 1, [t]) # Estado final # ============ # esFinal(e) se verifica si e es un estado final. def esFinal(e: Estado) -> bool: (_, _, ts) = e return ts[0] == tableroFinal # Sucesores # ========= # posicionesVecinas(p) son las posiciones de la matriz cuadrada de # dimensión 3 que se encuentran encima, abajo, a la izquierda y a la # derecha de los posición p. Por ejemplo, # >>> posicionesVecinas((1,1)) # [(0, 1), (2, 1), (1, 0), (1, 2)] # >>> posicionesVecinas((0,1)) # [(1, 1), (0, 0), (0, 2)] # >>> posicionesVecinas((0,0)) # [(1, 0), (0, 1)] def posicionesVecinas(p: Posicion) -> list[Posicion]: (i, j) = p vecinas = [] if i > 0: vecinas.append((i - 1, j)) if i < 2: vecinas.append((i + 1, j)) if j > 0: vecinas.append((i, j - 1)) if j < 2: vecinas.append((i, j + 1)) return vecinas # intercambia(t,p1, p2) es el tablero obtenido intercambiando en t los # elementos que se encuentran en las posiciones p1 y p2. Por ejemplo, # >>> intercambia([[2,1,3],[8,0,4],[7,6,5]], (0,1), (1,1)) # [[2, 0, 3], [8, 1, 4], [7, 6, 5]] def intercambia(t: Tablero, p1: Posicion, p2: Posicion) -> Tablero: (i1, j1) = p1 (i2, j2) = p2 t1 = deepcopy(t) a1 = t1[i1][j1] a2 = t1[i2][j2] t1[i1][j1] = a2 t1[i2][j2] = a1 return t1 # tablerosSucesores(t) es la lista de los tablrtos sucesores del # tablero t. Por ejemplo, # >>> tablerosSucesores([[2,1,3],[8,0,4],[7,6,5]]) # [[[2, 0, 3], [8, 1, 4], [7, 6, 5]], # [[2, 1, 3], [8, 6, 4], [7, 0, 5]], # [[2, 1, 3], [0, 8, 4], [7, 6, 5]], # [[2, 1, 3], [8, 4, 0], [7, 6, 5]]] def tablerosSucesores(t: Tablero) -> list[Tablero]: p = posicionHueco(t) return [intercambia(t, p, q) for q in posicionesVecinas(p)] # (sucesores e) es la lista de sucesores del estado e. Por ejemplo, # >>> t1 = [[0,1,3],[8,2,4],[7,6,5]] # >>> es = sucesores((heuristica(t1), 1, [t1])) # >>> es # [(4, 2, [[[8, 1, 3], # [0, 2, 4], # [7, 6, 5]], # [[0, 1, 3], # [8, 2, 4], # [7, 6, 5]]]), # (2, 2, [[[1, 0, 3], # [8, 2, 4], # [7, 6, 5]], # [[0, 1, 3], # [8, 2, 4], # [7, 6, 5]]])] # >>> sucesores(es[1]) # [(0, 3, [[[1, 2, 3], # [8, 0, 4], # [7, 6, 5]], # [[1, 0, 3], # [8, 2, 4], # [7, 6, 5]], # [[0, 1, 3], # [8, 2, 4], # [7, 6, 5]]]), # (4, 3, [[[1, 3, 0], # [8, 2, 4], # [7, 6, 5]], # [[1, 0, 3], # [8, 2, 4], # [7, 6, 5]], # [[0, 1, 3], # [8, 2, 4], # [7, 6, 5]]])] def sucesores(e: Estado) -> list[Estado]: (_, n, ts) = e return [(heuristica(t1), n+1, [t1] + ts) for t1 in tablerosSucesores(ts[0]) if t1 not in ts] # Solución # ======== def solucion_8puzzle(t: Tablero) -> Optional[list[Tablero]]: r = buscaPM(sucesores, esFinal, inicial(t)) if r is None: return None (_, _, ts) = r ts.reverse() return ts # Verificación # ============ def test_8puzzle() -> None: assert solucion_8puzzle([[8,1,3],[0,2,4],[7,6,5]]) == \ [[[8, 1, 3], [0, 2, 4], [7, 6, 5]], [[0, 1, 3], [8, 2, 4], [7, 6, 5]], [[1, 0, 3], [8, 2, 4], [7, 6, 5]], [[1, 2, 3], [8, 0, 4], [7, 6, 5]]] # La verificación es # src> poetry run pytest -q BPM_8Puzzle.py # 1 passed in 0.10s |