El problema de las fichas mediante búsqueda en espacio de estado
Para el problema de las fichas de orden (m,n) se considera un tablero con m+n+1 cuadrados consecutivos.
Inicialmente, en cada uno de los m primeros cuadrados hay una blanca, a continuación un hueco y en cada uno de los n últimos cuadrados hay una ficha verde. El objetivo consiste en tener las fichas verdes al principio y las blancas al final.
Por ejemplo, en el problema de las fichas de orden (3,3) el tablero inicial es
|
1 2 3 |
+---+---+---+---+---+---+---+ | B | B | B | | V | V | V | +---+---+---+---+---+---+---+ |
y el final es
|
1 2 3 |
+---+---+---+---+---+---+---+ | V | V | V | | B | B | B | +---+---+---+---+---+---+---+ |
Los movimientos permitidos consisten en desplazar una ficha al hueco saltando, como máximo, sobre otras dos.
Para representar el problema se definen los siguientes tipos de datos:
Fichacon tres constructoresB,VyHque representan las fichas blanca, verde y hueco, respectivamente.
|
1 2 |
data Ficha = B | V | H deriving (Eq, Show) |
Tableroque es una lista de fichas que representa las fichas colocadas en el tablero.
|
1 |
type Tablero = [Ficha] |
Estadorepresenta los estados del espacio de búsqueda, donde un estado es una lista de tableros [t(n), …, t(2), t(1)] tal que t(1) es el tablero inicial y para cada i (2 <= i <= n), t(i) es un sucesor de t(i-1).
|
1 2 |
newtype Estado = E [Tablero] deriving (Eq, Show) |
Busquedaes un procedimiento de búsqueda
|
1 2 3 4 |
type Busqueda = (Estado -> [Estado]) -> (Estado -> Bool) -> Estado -> [Estado] |
Además, se considera la heurística que para cada tablero vale la suma de piezas blancas situadas a la izquierda de cada una de las piezas verdes. Por ejemplo, para el estado
|
1 2 3 |
+---+---+---+---+---+---+---+ | B | V | B | | V | V | B | +---+---+---+---+---+---+---+ |
su valor es 1+2+2 = 5. La heurística de un estado es la del primero de sus tableros.
Usando los métodos de búsqueda estudiado en los ejercicios anteriores, definir la función
|
1 |
fichas :: Busqueda -> Int -> Int -> [[Tablero]] |
tal que fichas b m n es la lista de las soluciones del problema de las fichas de orden (m,n) obtenidas mediante el procedimiento de búsqueda b. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
λ> head (fichas buscaProfundidad 2 2) [[B,B,H,V,V],[B,H,B,V,V],[H,B,B,V,V],[V,B,B,H,V],[V,B,H,B,V],[V,H,B,B,V], [H,V,B,B,V],[B,V,H,B,V],[B,H,V,B,V],[H,B,V,B,V],[B,B,V,H,V],[B,B,V,V,H], [B,H,V,V,B],[H,B,V,V,B],[V,B,H,V,B],[V,H,B,V,B],[H,V,B,V,B],[B,V,H,V,B], [B,V,V,H,B],[H,V,V,B,B],[V,H,V,B,B],[V,V,H,B,B]] λ> head (fichas buscaAnchura 2 2) [[B,B,H,V,V],[B,B,V,V,H],[B,H,V,V,B],[B,V,V,H,B],[H,V,V,B,B], [V,V,H,B,B]] λ> head (fichas buscaPM 2 2) [[B,B,H,V,V],[B,H,B,V,V],[B,V,B,H,V],[H,V,B,B,V],[V,H,B,B,V], [V,V,B,B,H],[V,V,B,H,B],[V,V,H,B,B]] λ> head (fichas buscaEscalada 2 2) [[B,B,H,V,V],[B,H,B,V,V],[B,V,B,H,V],[H,V,B,B,V],[V,H,B,B,V], [V,V,B,B,H],[V,V,B,H,B],[V,V,H,B,B]] |
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 |
module BEE_El_problema_de_las_fichas where import BusquedaEnProfundidad (buscaProfundidad) import BusquedaEnAnchura (buscaAnchura) import BusquedaPrimeroElMejor (buscaPM) import BusquedaEnEscalada (buscaEscalada) import Test.Hspec (Spec, hspec, it, shouldBe) -- Representación del problema -- =========================== data Ficha = B | V | H deriving (Eq, Show) type Tablero = [Ficha] -- (tableroInicial m n) representa el tablero inicial del problema de las fichas -- de orden (m,n). Por ejemplo, -- tableroInicial 2 3 == [B,B,H,V,V,V] -- tableroInicial 3 2 == [B,B,B,H,V,V] tableroInicial :: Int -> Int -> Tablero tableroInicial m n = replicate m B ++ [H] ++ replicate n V -- (tableroFinal m n) representa el tablero final del problema de las fichas de -- orden (m,n). Por ejemplo, -- tableroFinal 2 3 == [V,V,V,H,B,B] -- tableroFinal 3 2 == [V,V,H,B,B,B] tableroFinal :: Int -> Int -> Tablero tableroFinal m n = replicate n V ++ [H] ++ replicate m B -- (tablerosSucesores t) es la lista de los sucesores del tablero t. Por -- ejemplo, -- λ> tablerosSucesores [V,B,H,V,V,B] -- [[V,H,B,V,V,B],[H,B,V,V,V,B],[V,B,V,H,V,B],[V,B,V,V,H,B], -- [V,B,B,V,V,H]] -- λ> tablerosSucesores [B,B,B,H,V,V,V] -- [[B,B,H,B,V,V,V],[B,H,B,B,V,V,V],[H,B,B,B,V,V,V], -- [B,B,B,V,H,V,V],[B,B,B,V,V,H,V],[B,B,B,V,V,V,H]] tablerosSucesores :: Tablero -> [Tablero] tablerosSucesores t = [intercambia i j t | i <- [j-1,j-2,j-3,j+1,j+2,j+3] , 0 <= i, i < n] where j = posicionHueco t n = length t -- (posicionHueco t) es la posición del hueco en el tablero t. Por -- ejemplo, -- posicionHueco (tableroInicial 3 2) == 3 posicionHueco :: Tablero -> Int posicionHueco t = length (takeWhile (/=H) t) -- (intercambia xs i j) es la lista obtenida intercambiando los -- elementos de xs en las posiciones i y j. Por ejemplo, -- intercambia 2 6 [0..9] == [0,1,6,3,4,5,2,7,8,9] -- intercambia 6 2 [0..9] == [0,1,6,3,4,5,2,7,8,9] intercambia :: Int -> Int -> [a] -> [a] intercambia i j xs = concat [xs1,[x2],xs2,[x1],xs3] where (xs1,x1,xs2,x2,xs3) = divide (min i j) (max i j) xs -- (divide xs i j) es la tupla (xs1,x1,xs2,x2,xs3) tal que xs1 son los -- elementos de xs cuya posición es menor que i, x1 es el elemento de xs -- en la posición i, xs2 son los elementos de xs cuya posición es mayor -- que i y menor que j, x2 es el elemento de xs en la posición j y xs3 -- son los elementos de xs cuya posición es mayor que j (suponiendo que -- i < j). Por ejemplo, -- divide 2 6 [0..9] == ([0,1],2,[3,4,5],6,[7,8,9]) divide :: Int -> Int -> [a] -> ([a],a,[a],a,[a]) divide i j xs = (xs1,x1,xs2,x2,xs3) where (xs1,x1:ys) = splitAt i xs (xs2,x2:xs3) = splitAt (j - i - 1) ys newtype Estado = E [Tablero] deriving (Eq, Show) -- (inicial m n) representa el estado inicial del problema de las fichas -- de orden (m,n). Por ejemplo, -- inicial 2 3 == E [[B,B,H,V,V,V]] -- inicial 3 2 == E [[B,B,B,H,V,V]] inicial :: Int -> Int -> Estado inicial m n = E [tableroInicial m n] -- (esFinal m n e) se verifica si e es un estado final del problema de las -- fichas de orden (m,n). Por ejemplo, -- λ> esFinal 2 1 (E [[V,H,B,B],[V,B,B,H],[H,B,B,V],[B,B,H,V]]) -- True -- λ> esFinal 2 1 (E [[V,B,B,H],[H,B,B,V],[B,B,H,V]]) -- False esFinal :: Int -> Int -> Estado -> Bool esFinal m n (E (e:_)) = e == tableroFinal m n -- (sucesores n) es la lista de los sucesores del estado n. Por ejemplo, -- λ> sucesores (E [[H,B,B,V],[B,B,H,V]]) -- [E [[B,H,B,V],[H,B,B,V],[B,B,H,V]], -- E [[V,B,B,H],[H,B,B,V],[B,B,H,V]]] -- λ> sucesores (E [[B,H,B,V],[H,B,B,V],[B,B,H,V]]) -- [E [[B,V,B,H],[B,H,B,V],[H,B,B,V],[B,B,H,V]]] sucesores :: Estado -> [Estado] sucesores (E e@(t:ts)) = [E (t':e) | t' <- tablerosSucesores t, t' `notElem` ts] -- Heurística -- ========== -- (heuristicaT t) es la heurística del tablero t. Por ejemplo, -- heuristicaT [B,V,B,H,V,V,B] == 5 heuristicaT :: Tablero -> Int heuristicaT [] = 0 heuristicaT (V:xs) = heuristicaT xs heuristicaT (H:xs) = heuristicaT xs heuristicaT (B:xs) = heuristicaT xs + length (filter (==V) xs) -- (heuristica e) es la heurística del primer tablero del estado e. Por -- ejemplo, -- heuristica (E [[H,B,B,V],[B,B,H,V]]) == 2 -- heuristica (E [[V,B,B,H],[H,B,B,V],[B,B,H,V]]) == 0 heuristica :: Estado -> Int heuristica (E (t:_)) = heuristicaT t -- Estado es un subtipo de Ord de forma que un estado es menor o igual -- que otro si su heurística lo es. instance Ord Estado where e1 <= e2 = heuristica e1 <= heuristica e2 -- Solución por búsqueda -- ===================== type Busqueda = (Estado -> [Estado]) -> (Estado -> Bool) -> Estado -> [Estado] fichas :: Busqueda -> Int -> Int -> [[Tablero]] fichas b m n = [reverse es | E es <- b sucesores (esFinal m n) (inicial m n)] -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ head (fichas buscaProfundidad 2 2) `shouldBe` [[B,B,H,V,V],[B,H,B,V,V],[H,B,B,V,V],[V,B,B,H,V],[V,B,H,B,V],[V,H,B,B,V], [H,V,B,B,V],[B,V,H,B,V],[B,H,V,B,V],[H,B,V,B,V],[B,B,V,H,V],[B,B,V,V,H], [B,H,V,V,B],[H,B,V,V,B],[V,B,H,V,B],[V,H,B,V,B],[H,V,B,V,B],[B,V,H,V,B], [B,V,V,H,B],[H,V,V,B,B],[V,H,V,B,B],[V,V,H,B,B]] it "e2" $ head (fichas buscaAnchura 2 2) `shouldBe` [[B,B,H,V,V],[B,B,V,V,H],[B,H,V,V,B],[B,V,V,H,B],[H,V,V,B,B],[V,V,H,B,B]] it "e3" $ head (fichas buscaPM 2 2) `shouldBe` [[B,B,H,V,V],[B,H,B,V,V],[B,V,B,H,V],[H,V,B,B,V],[V,H,B,B,V],[V,V,B,B,H], [V,V,B,H,B],[V,V,H,B,B]] it "e4" $ head (fichas buscaEscalada 2 2) `shouldBe` [[B,B,H,V,V],[B,H,B,V,V],[B,V,B,H,V],[H,V,B,B,V],[V,H,B,B,V],[V,V,B,B,H], [V,V,B,H,B],[V,V,H,B,B]] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- -- Finished in 0.0055 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 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 |
from enum import Enum from functools import partial from typing import Callable, Optional from src.BusquedaEnAnchura import buscaAnchura1 from src.BusquedaEnEscalada import buscaEscalada from src.BusquedaEnProfundidad import buscaProfundidad1 from src.BusquedaPrimeroElMejor import buscaPM # Representación del problema # =========================== class Ficha(Enum): B = 0 V = 1 H = 2 def __repr__(self) -> str: return self.name B = Ficha.B V = Ficha.V H = Ficha.H Tablero = list[Ficha] # tableroInicial(m, n) representa el tablero inicial del problema de las fichas # de orden (m,n). Por ejemplo, # tableroInicial(2, 3) == [B,B,H,V,V,V] # tableroInicial(3, 2) == [B,B,B,H,V,V] def tableroInicial(m: int, n: int) -> Tablero: return [B]*m + [H] + [V]*n # tableroFinal(m, n) representa el tablero final del problema de las fichas de # orden (m,n). Por ejemplo, # tableroFinal(2, 3) == [V,V,V,H,B,B] # tableroFinal(3, 2) == [V,V,H,B,B,B] def tableroFinal(m: int, n: int) -> Tablero: return [V]*n + [H] + [B]*m # posicionHueco(t) es la posición del hueco en el tablero t. Por # ejemplo, # posicionHueco(tableroInicial(3, 2)) == 3 def posicionHueco(t: Tablero) -> int: return t.index(H) # intercambia(xs, i, j) es la lista obtenida intercambiando los # elementos de xs en las posiciones i y j. Por ejemplo, # intercambia(1, 3, tableroInicial(3, 2)) == [B, H, B, B, V, V] def intercambia(i: int, j: int, t: Tablero) -> Tablero: t1 = t.copy() t1[i], t1[j] = t1[j], t1[i] return t1 # tablerosSucesores(t) es la lista de los sucesores del tablero t. Por # ejemplo, # >>> tablerosSucesores([V,B,H,V,V,B]) # [[V,H,B,V,V,B],[H,B,V,V,V,B],[V,B,V,H,V,B],[V,B,V,V,H,B], # [V,B,B,V,V,H]] # >>> tablerosSucesores([B,B,B,H,V,V,V]) # [[B,B,H,B,V,V,V],[B,H,B,B,V,V,V],[H,B,B,B,V,V,V], # [B,B,B,V,H,V,V],[B,B,B,V,V,H,V],[B,B,B,V,V,V,H]] def tablerosSucesores(t: Tablero) -> list[Tablero]: j = posicionHueco(t) n = len(t) return [intercambia(i, j, t) for i in [j-1,j-2,j-3,j+1,j+2,j+3] if 0 <= i < n] # Heurística # ========== # heuristicaT(t) es la heurística del tablero t. Por ejemplo, # heuristicaT([B,V,B,H,V,V,B]) == 5 def heuristicaT(t: Tablero) -> int: if not t: return 0 f, *fs = t if f in {V, H}: return heuristicaT(fs) return heuristicaT(fs) + len([x for x in fs if x == V]) class Estado(list[Tablero]): def __lt__(self, e: list[Tablero]) -> bool: return heuristicaT(self[0]) < heuristicaT(e[0]) # inicial(m, n) representa el estado inicial del problema de las fichas # de orden (m,n). Por ejemplo, # inicial(2, 3) == [[B,B,H,V,V,V]] # inicial(3, 2) == [[B,B,B,H,V,V]] def inicial(m: int, n: int) -> Estado: return Estado([tableroInicial(m, n)]) # esFinal(m, n, e) se verifica si e es un estado final del problema de las # fichas de orden (m,n). Por ejemplo, # >>> esFinal(2, 1, [[V,H,B,B],[V,B,B,H],[H,B,B,V],[B,B,H,V]]) # True # >>> esFinal(2, 1, [[V,B,B,H],[H,B,B,V],[B,B,H,V]]) # False def esFinal(m: int, n: int, e: Estado) -> bool: return e[0] == tableroFinal(m, n) # (sucesores n) es la lista de los sucesores del estado n. Por ejemplo, # >>> sucesores([[H,B,B,V],[B,B,H,V]]) # [[[B,H,B,V],[H,B,B,V],[B,B,H,V]], # [[V,B,B,H],[H,B,B,V],[B,B,H,V]]] # >>> sucesores([[B,H,B,V],[H,B,B,V],[B,B,H,V]]) # [[[B,V,B,H],[B,H,B,V],[H,B,B,V],[B,B,H,V]]] def sucesores(e: Estado) -> list[Estado]: t, *ts = e return [Estado([t1] + e) for t1 in tablerosSucesores(t) if t1 not in ts] # Solución por búsqueda # ===================== Busqueda = Callable[[Callable[[Estado], list[Estado]], Callable[[Estado], bool], Estado], Optional[Estado]] def fichas(b: Busqueda, m: int, n: int) -> Optional[list[Tablero]]: r = partial(b, sucesores, lambda e: esFinal(m, n, e), inicial(m, n))() if r is None: return None return [list(reversed(es)) for es in r] # Verificación # ============ def test_fichas() -> None: assert fichas(buscaProfundidad1, 1, 2) == \ [[B, H, V, V], [B, V, V, H], [H, V, V, B], [V, V, H, B]] assert fichas(buscaAnchura1, 1, 2) == \ [[B, H, V, V], [B, V, V, H], [H, V, V, B], [V, V, H, B]] assert fichas(buscaPM, 1, 2) == \ [[B, H, V, V], [B, V, H, V], [H, V, B, V], [V, V, B, H], [V, V, H, B]] assert fichas(buscaEscalada, 1, 2) == \ [[B, H, V, V], [H, B, V, V], [V, B, H, V], [V, H, B, V], [V, V, B, H], [V, V, H, B]] print("Verificado") # La verificación es # >>> test_fichas() # Verificado |