El problema del granjero mediante búsqueda en espacio de estado
Un granjero está parado en un lado del río y con él tiene un una cabra y una repollo. En el río hay un barco pequeño. El desea cruzar el río con sus tres posesiones. No hay puentes y en el barco hay solamente sitio para el granjero y un artículo. Si deja la cabra con la repollo sola en un lado del río la cabra comerá la repollo. Si deja el lobo y la cabra en un lado, el lobo se comerá a la cabra. ¿Cómo puede cruzar el granjero el río con los tres artículos, sin que ninguno se coma al otro?
Para representar el problema se definen los siguientes tipos de dato:
Orillacon dos constructores (IyD) que representan las orillas izquierda y derecha, respectivamente.Estadoque es una tupla que representa en qué orilla se encuentra cada uno de los elementos (granjero, lobo, cabra, repollo). Por ejemplo,(I,D,D,I)representa que el granjero está en la izquierda, que el lobo está en la derecha, que la cabra está en la derecha y el repollo está en la izquierda.
Usando el procedimiento de búsqueda en profundidad, definir la función
|
1 |
granjero :: [[Estado]] |
tal que granjero son las soluciones del problema del granjero mediante el patrón de búsqueda en espacio de estados. Por ejemplo,
|
1 2 3 4 5 |
λ> head granjero [(I,I,I,I),(D,I,D,I),(I,I,D,I),(D,D,D,I), (I,D,I,I),(D,D,I,D),(I,D,I,D),(D,D,D,D)] λ> length granjero 2 |
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 |
module BEE_El_problema_del_granjero where import BusquedaEnProfundidad (buscaProfundidad) import Test.Hspec (Spec, hspec, it, shouldBe) data Orilla = I | D deriving (Eq, Show) type Estado = (Orilla,Orilla,Orilla,Orilla) -- (seguro e) se verifica si el estado e es seguro; es decir, que no -- puede estar en una orilla el lobo con la cabra sin el granjero ni la -- cabra con el repollo sin el granjero. Por ejemplo, -- seguro (I,D,D,I) == False -- seguro (D,D,D,I) == True -- seguro (D,D,I,I) == False -- seguro (I,D,I,I) == True seguro :: Estado -> Bool seguro (g,l,c,r) = not (g /= c && (c == l || c == r)) -- (opuesta x) es la opuesta de la orilla x. Por ejemplo -- opuesta I = D opuesta :: Orilla -> Orilla opuesta I = D opuesta D = I -- (sucesoresE e) es la lista de los sucesores seguros del estado e. Por -- ejemplo, -- sucesoresE (I,I,I,I) == [(D,I,D,I)] -- sucesoresE (D,I,D,I) == [(I,I,D,I),(I,I,I,I)] sucesoresE :: Estado -> [Estado] sucesoresE e = [mov e | mov <- [m1,m2,m3,m4], seguro (mov e)] where m1 (g,l,c,r) = (opuesta g, l, c, r) m2 (g,l,c,r) = (opuesta g, opuesta l, c, r) m3 (g,l,c,r) = (opuesta g, l, opuesta c, r) m4 (g,l,c,r) = (opuesta g, l, c, opuesta r) -- Nodo es el tipo de los nodos del espacio de búsqueda, donde un nodo -- es una lista de estados -- [e_n, ..., e_2, e_1] -- tal que e_1 es el estado inicial y para cada i (2 <= i <= n), e_i es un -- sucesor de e_(i-1). newtype Nodo = Nodo [Estado] deriving (Eq, Show) -- inicial es el nodo inicial en el que todos están en la orilla -- izquierda. inicial :: Nodo inicial = Nodo [(I,I,I,I)] -- (esFinal n) se verifica si n es un nodo final; es decir, su primer -- elemento es el estado final. Por ejemplo, -- esFinal (Nodo [(D,D,D,D),(I,I,I,I)]) == True -- esFinal (Nodo [(I,I,D,I),(I,I,I,I)]) == False esFinal :: Nodo -> Bool esFinal (Nodo (n:_)) = n == (D,D,D,D) -- (sucesores n) es la lista de los sucesores del nodo n. Por ejemplo, -- λ> sucesores (Nodo [(I,I,D,I),(D,I,D,I),(I,I,I,I)]) -- [Nodo [(D,D,D,I),(I,I,D,I),(D,I,D,I),(I,I,I,I)], -- Nodo [(D,I,D,D),(I,I,D,I),(D,I,D,I),(I,I,I,I)]] sucesores :: Nodo -> [Nodo] sucesores (Nodo n@(e:es)) = [Nodo (e':n) | e' <- sucesoresE e, e' `notElem` es] granjero :: [[Estado]] granjero = [reverse es | (Nodo es) <- buscaProfundidad sucesores esFinal inicial] -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ head granjero `shouldBe` [(I,I,I,I),(D,I,D,I),(I,I,D,I),(D,D,D,I), (I,D,I,I),(D,D,I,D),(I,D,I,D),(D,D,D,D)] it "e2" $ length granjero `shouldBe` 2 -- La verificación es -- λ> verifica -- -- e1 -- e2 -- -- Finished in 0.0008 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 |
from enum import Enum from src.BusquedaEnProfundidad import buscaProfundidad class Orilla(Enum): I = 0 D = 1 def __repr__(self) -> str: return self.name I = Orilla.I D = Orilla.D Estado = tuple[Orilla, Orilla, Orilla, Orilla] # seguro(e) se verifica si el estado e es seguro; es decir, que no # puede estar en una orilla el lobo con la cabra sin el granjero ni la # cabra con el repollo sin el granjero. Por ejemplo, # seguro((I,D,D,I)) == False # seguro((D,D,D,I)) == True # seguro((D,D,I,I)) == False # seguro((I,D,I,I)) == True def seguro(e: Estado) -> bool: (g,l,c,r) = e return not (g != c and c in {l, r}) # (opuesta x) es la opuesta de la orilla x. Por ejemplo # opuesta(I) == D def opuesta(o: Orilla) -> Orilla: if o == I: return D return I # sucesoresE(e) es la lista de los sucesores seguros del estado e. Por # ejemplo, # sucesoresE((I,I,I,I)) == [(D,I,D,I)] # sucesoresE((D,I,D,I)) == [(I,I,D,I),(I,I,I,I)] def sucesoresE(e: Estado) -> list[Estado]: def mov(n: int, e: Estado) -> Estado: (g,l,c,r) = e if n == 1: return (opuesta(g), l, c, r) if n == 2: return (opuesta(g), opuesta(l), c, r) if n == 3: return (opuesta(g), l, opuesta(c), r) return (opuesta(g), l, c, opuesta(r)) return [mov(n, e) for n in range(1, 5) if seguro(mov(n, e))] # Nodo es el tipo de los nodos del espacio de búsqueda, donde un nodo # es una lista de estados # [e_n, ..., e_2, e_1] # tal que e_1 es el estado inicial y para cada i (2 <= i <= n), e_i es un # sucesor de e_(i-1). Nodo = list[Estado] # inicial es el nodo inicial en el que todos están en la orilla # izquierda. inicial: Nodo = [(I,I,I,I)] # esFinal(n) se verifica si n es un nodo final; es decir, su primer # elemento es el estado final. Por ejemplo, # esFinal([(D,D,D,D),(I,I,I,I)]) == True # esFinal([(I,I,D,I),(I,I,I,I)]) == False def esFinal(n: Nodo) -> bool: return n[0] == (D,D,D,D) # sucesores(n) es la lista de los sucesores del nodo n. Por ejemplo, # >>> sucesores([(I,I,D,I),(D,I,D,I),(I,I,I,I)]) # [[(D, D, D, I), (I, I, D, I), (D, I, D, I), (I, I, I, I)], # [(D, I, D, D), (I, I, D, I), (D, I, D, I), (I, I, I, I)]] def sucesores(n: Nodo) -> list[Nodo]: e, *es = n return [[e1] + n for e1 in sucesoresE(e) if e1 not in es] def granjero() -> list[list[Estado]]: return [list(reversed(es)) for es in buscaProfundidad(sucesores, esFinal, inicial)] # # Verificación # # ============ def test_granjero() -> None: assert granjero() == \ [[(I,I,I,I),(D,I,D,I),(I,I,D,I),(D,I,D,D),(I,I,I,D),(D,D,I,D),(I,D,I,D),(D,D,D,D)], [(I,I,I,I),(D,I,D,I),(I,I,D,I),(D,D,D,I),(I,D,I,I),(D,D,I,D),(I,D,I,D),(D,D,D,D)]] print("Verificado") # La verificación es # >>> test_granjero() # Verificado |