Definir la sucesión
|
1 |
sumasDeDosPrimos :: [Integer] |
cuyos elementos son los números que se pueden escribir como suma de dos números primos. Por ejemplo,
|
1 2 3 4 |
λ> take 23 sumasDeDosPrimos [4,5,6,7,8,9,10,12,13,14,15,16,18,19,20,21,22,24,25,26,28,30,31] λ> sumasDeDosPrimos !! (5*10^5) 862878 |
Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, …
Un primo de Hilbert es un número de Hilbert n que no es divisible por ningún número de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, …
Definir la función
|
1 |
factorizacionesH :: Integer -> [[Integer]] |
tal que factorizacionesH n es la listas de primos de Hilbert cuyo producto es el número de Hilbert n. Por ejemplo,
|
1 2 3 4 |
factorizacionesH 25 == [[5,5]] factorizacionesH 45 == [[5,9]] factorizacionesH 441 == [[9,49],[21,21]] factorizacionesH 80109 == [[9,9,989],[9,69,129]] |
Comprobar con QuickCheck que todos los números de Hilbert son factorizables como producto de primos de Hilbert (aunque la factorización, como para el 441, puede no ser única).
Read More «Factorizaciones de números de Hilbert»
Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97, …
Un primo de Hilbert es un número de Hilbert n que no es divisible por ningún número de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, 141, 149, 157, 161, 173, 177, 181, 193, 197, …
Definir la sucesión
|
1 |
primosH :: [Integer] |
tal que sus elementos son los primos de Hilbert. Por ejemplo,
|
1 2 |
take 15 primosH == [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73] primosH !! (3*10^4) == 313661 |
El 25 de diciembre de 1640, en una carta a Mersenne, Fermat demostró la conjetura de Girard: todo primo de la forma 4n+1 puede expresarse de manera única como suma de dos cuadrados. Por eso es conocido como el teorema de Navidad de Fermat.
Definir las funciones
|
1 2 3 |
representaciones :: Integer -> [(Integer,Integer)] primosImparesConRepresentacionUnica :: [Integer] primos4nM1 :: [Integer] |
tales que
representaciones n es la lista de pares de números naturales (x,y) tales que n = x^2 + y^2 con x <= y. Por ejemplo.|
1 2 3 4 5 6 |
representaciones 20 == [(2,4)] representaciones 25 == [(0,5),(3,4)] representaciones 325 == [(1,18),(6,17),(10,15)] representaciones 100000147984 == [(0,316228)] length (representaciones (10^10)) == 6 length (representaciones (4*10^12)) == 7 |
primosImparesConRepresentacionUnica es la lista de los números primos impares que se pueden escribir exactamente de una manera como suma de cuadrados de pares de números naturales (x,y) con x <= y. Por ejemplo,|
1 2 |
λ> take 20 primosImparesConRepresentacionUnica [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193] |
primos4nM1 es la lista de los números primos que se pueden escribir como uno más un múltiplo de 4 (es decir, que son congruentes con 1 módulo 4). Por ejemplo,|
1 2 |
λ> take 20 primos4nM1 [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193] |
El teorema de Navidad de Fermat afirma que un número primo impar p se puede escribir exactamente de una manera como suma de dos cuadrados de números naturales p = x² + y² (con x <= y) si, y sólo si, p se puede escribir como uno más un múltiplo de 4 (es decir, que es congruente con 1 módulo 4).
Comprobar con QuickCheck el teorema de Navidad de Fermat; es decir, que para todo número n, los n-ésimos elementos de
primosImparesConRepresentacionUnica y de primos4nM1 son iguales.
Read More «El teorema de Navidad de Fermat»
Los números de Fibonacci se definen mediante las ecuaciones
|
1 2 3 |
F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2), si n > 1 |
Los primeros números de Fibonacci son
|
1 |
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ... |
Una generalización de los anteriores son los números de Pentanacci definidos por las siguientes ecuaciones
|
1 2 3 4 5 6 |
P(0) = 0 P(1) = 1 P(2) = 1 P(3) = 2 P(4) = 4 P(n) = P(n-1) + P(n-2) + P(n-3) + P(n-4) + P(n-5), si n > 4 |
Los primeros números de Pentanacci son
|
1 |
0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ... |
Definir las funciones
|
1 2 |
pentanacci :: Integer -> Integer pentanaccis :: [Integer] |
tales que
pentanacci n es el n-ésimo número de Pentanacci. Por ejemplo,|
1 2 3 4 5 6 |
λ> pentanacci 14 3525 λ> pentanacci (10^5) `mod` 10^30 482929150584077921552549215816 λ> length (show (pentanacci (10^5))) 29357 |
pentanaccis es la lista de los números de Pentanacci. Por ejemplo,|
1 2 |
λ> take 15 pentanacci [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525] |
Un sistema de ecuaciones lineales \(Ax = b\) es triangular inferior si todos los elementos de la matriz \(A\) que están por encima de la diagonal principal son nulos; es decir, es de la forma
\begin{align}
&a_{1 1}x_1 &= b_1 \\
&a_{2 1}x_1 + a_{2 2}x_2 &= b_2 \\
&a_{3 1}x_1 + a_{3 2}x_2 + a_{3 3}x_3 &= b_3 \\
&… & \\
&a_{n 1}x_1 + a_{n 2}x_2 + a_{n 3}x_3 +…+ a_{n n}x_n &= b_n
\end{align}
El sistema es compatible si, y sólo si, el producto de los elementos de la diagonal principal es distinto de cero. En este caso, la solución se puede calcular mediante el algoritmo de bajada:
\begin{align}
x_1 &= \frac{b_1}{a_{1 1}} \\
x_2 &= \frac{b_2 – a_{2 1}x_1}{a_{2 2}} \\
x_3 &= \frac{b_3 – a_{3 1}x_1 – a_{3 2}x_2}{a_{3 3}} \\
… \\
x_n &= \frac{b_n – a_{n 1}x_1 – a_{n 2}x_2 – … – a_{n,n-1}x_{n-1}}{a_{n n}}
\end{align}
Definir la función
|
1 |
bajada :: Matrix Double -> Matrix Double -> Matrix Double |
tal que bajada a b es la solución, mediante el algoritmo de bajada, del sistema compatible triangular superior ax = b. Por ejemplo,
|
1 2 3 4 5 6 |
λ> let a = fromLists [[2,0,0],[3,1,0],[4,2,5.0]] λ> let b = fromLists [[3],[6.5],[10]] λ> bajada a b ( 1.5 ) ( 2.0 ) ( 0.0 ) |
Es decir, la solución del sistema
\begin{align}
2x &= 3 \\
3x + y &= 6.5 \\
4x + 2y + 5z &= 10
\end{align}
es \(x=1.5\), \(y=2\) y \(z=0\).
Read More «Algoritmo de bajada para resolver un sistema triangular inferior»
La integral definida de una función f entre los límites a y b puede calcularse mediante la regla del rectángulo (ver en http://bit.ly/1FDhZ1z) usando la fórmula
\[ h(f(a+\frac{h}{2}) + f(a+h+\frac{h}{2}) + f(a+2h+\frac{h}{2}) + … + f(a+nh+\frac{h}{2}))\]
con \(a+nh+\dfrac{h}{2} \leq b < a+(n+1)h+\dfrac{h}{2}\) y usando valores pequeños para \(h\).
Definir la función
|
1 |
integral :: (Fractional a, Ord a) => a -> a -> (a -> a) -> a -> a |
tal que integral a b f h es el valor de dicha expresión. Por ejemplo, el cálculo de la integral de (f(x) = x^3) entre 0 y 1, con paso 0.01, es
|
1 |
integral 0 1 (^3) 0.01 == 0.24998750000000042 |
Otros ejemplos son
|
1 2 3 4 |
integral 0 1 (^4) 0.01 == 0.19998333362500048 integral 0 1 (\x -> 3*x^2 + 4*x^3) 0.01 == 1.9999250000000026 log 2 - integral 1 2 (\x -> 1/x) 0.01 == 3.124931644782336e-6 pi - 4 * integral 0 1 (\x -> 1/(x^2+1)) 0.01 == -8.333333331389525e-6 |
Definir la función
|
1 |
raizEnt :: Integer -> Integer -> Integer |
tal que raizEnt x n es la raíz entera n-ésima de x; es decir, el mayor número entero y tal que \(y^n \leq x\). Por ejemplo,
|
1 2 3 4 5 |
raizEnt 8 3 == 2 raizEnt 9 3 == 2 raizEnt 26 3 == 2 raizEnt 27 3 == 3 raizEnt (10^50) 2 == 10000000000000000000000000 |
Comprobar con QuickCheck que para todo número natural n,
|
1 |
raizEnt (10^(2*n)) 2 == 10^n |
El método de bisección para calcular una raíz de una función en el intervalo [a,b] se basa en el teorema de Bolzano:
Si f(x) es una función continua en el intervalo \([a, b]\), y si, además, en los extremos del intervalo la función \(f\) toma valores de signo opuesto \((f(a)f(b) < 0)\), entonces existe al menos un valor \(c\) en \((a, b)\) para el que \(f(c) = 0\)».
El método para calcular una raíz de la función \(f\) en el intervalo \([a,b]\) con un error menor que \(e\) consiste en tomar el punto medio del intervalo \(c = \frac{a+b}{2}\) y considerar los siguientes casos:
Definir la función
|
1 |
biseccion :: (Double -> Double) -> Double -> Double -> Double -> Double |
tal que biseccion f a b e es una aproximación del punto del intervalo [a,b] en el que se anula la función f, con un error menor que e, calculada mediante el método de la bisección. Por ejemplo,
|
1 2 3 4 |
biseccion (\x -> x^2 - 3) 0 5 0.01 == 1.7333984375 biseccion (\x -> x^3 - x - 2) 0 4 0.01 == 1.521484375 biseccion cos 0 2 0.01 == 1.5625 biseccion (\x -> log (50-x) - 4) (-10) 3 0.01 == -5.125 |
Read More «Método de bisección para calcular raíces de una función»
Definir la función
|
1 |
limite :: (Double -> Double) -> Double -> Double |
tal que limite f a es el valor de f en el primer término x tal que, para todo y entre x+1 y x+100, el valor absoluto de la diferencia entre f(y) y f(x) es menor que a. Por ejemplo,
|
1 2 |
limite (\n -> (2*n+1)/(n+5)) 0.001 == 1.9900110987791344 limite (\n -> (1+1/n)**n) 0.001 == 2.714072874546881 |
Definir, usando puntoCero, la función
|
1 |
inversa :: (Double -> Double) -> Double -> Double |
tal que inversa g x es el valor de la inversa de g en x. Por ejemplo,
|
1 |
inversa (^2) 9 == 3.000000002941184 |
Definir, usando inversa, las funciones raizCuadrada, raizCubica, arcoseno y arcocoseno que calculen la raíz cuadrada, la raíz cúbica, el arco seno y el arco coseno, respectivamente. Por ejemplo,
|
1 2 3 4 |
raizCuadrada 9 == 3.000000002941184 raizCubica 27 == 3.0000000000196048 arcoseno 1 == 1.5665489428306574 arcocoseno 0 == 1.5707963267949576 |
Los ceros de una función pueden calcularse mediante el método de Newton basándose en las siguientes propiedades:
Definir la función
|
1 |
puntoCero :: (Double -> Double) -> Double |
tal que puntoCero f es un cero de la función f calculado usando la propiedad anterior. Por ejemplo,
|
1 |
puntoCero cos == 1.5707963267949576 |
El método de Herón para calcular la raíz cuadrada de un número se basa en las siguientes propiedades:
Definir la función
|
1 |
raiz :: Double -> Double |
tal que raiz x es la raíz cuadrada de x calculada usando la propiedad anterior con una aproximación de 0.00001 y tomando como valor inicial 1. Por ejemplo,
|
1 |
raiz 9 == 3.000000001396984 |
Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz
|
1 2 3 |
( 1 6 11 2 ) ( 7 12 3 8 ) ( 3 8 4 9 ) |
moviéndose en cada paso una casilla hacia la derecha o hacia abajo, son los siguientes:
|
1 2 3 4 5 6 7 8 9 10 |
[1,6,11,2,8,9] [1,6,11,3,8,9] [1,6,12,3,8,9] [1,7,12,3,8,9] [1,6,11,3,4,9] [1,6,12,3,4,9] [1,7,12,3,4,9] [1,6,12,8,4,9] [1,7,12,8,4,9] [1,7, 3,8,4,9] |
La suma de los caminos son 37, 38, 39, 40, 34, 35, 36, 40, 41 y 32, respectivamente. El camino de máxima suma es el penúltimo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.
Definir la función
|
1 |
caminoMaxSuma :: Matrix Int -> [Int] |
tal que caminoMaxSuma m es un camino de máxima suma en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,
|
1 2 3 4 |
λ> caminoMaxSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) [1,7,12,8,4,9] λ> sum (caminoMaxSuma (fromList 500 500 [1..])) 187001249 |
Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz
|
1 2 3 |
( 1 6 11 2 ) ( 7 12 3 8 ) ( 3 8 4 9 ) |
moviéndose en cada paso una casilla hacia la derecha o hacia abajo, son los siguientes:
|
1 2 3 4 5 6 7 8 9 10 |
[1,6,11,2,8,9] [1,6,11,3,8,9] [1,6,12,3,8,9] [1,7,12,3,8,9] [1,6,11,3,4,9] [1,6,12,3,4,9] [1,7,12,3,4,9] [1,6,12,8,4,9] [1,7,12,8,4,9] [1,7, 3,8,4,9] |
La suma de los caminos son 37, 38, 39, 40, 34, 35, 36, 40, 41 y 32, respectivamente. El camino de máxima suma es el penúltimo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.
Definir la función
|
1 |
maximaSuma :: Matrix Int -> Int |
tal que maximaSuma m es el máximo de las sumas de los caminos en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia a derecha. Por ejemplo,
|
1 2 3 4 |
λ> maximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) 41 λ> maximaSuma (fromList 800 800 [1..]) 766721999 |
Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz
|
1 2 3 |
( 1 6 11 2 ) ( 7 12 3 8 ) ( 3 8 4 9 ) |
moviéndose en cada paso una casilla hacia la derecha o abajo, son los siguientes:
|
1 2 3 4 5 6 7 8 9 10 |
[1,6,11,2,8,9] [1,6,11,3,8,9] [1,6,12,3,8,9] [1,7,12,3,8,9] [1,6,11,3,4,9] [1,6,12,3,4,9] [1,7,12,3,4,9] [1,6,12,8,4,9] [1,7,12,8,4,9] [1,7, 3,8,4,9] |
Definir la función
|
1 |
caminos :: Matrix Int -> [[Int]] |
tal que caminos m es la lista de los caminos en la matriz m desde extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia la derecha o abajo. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
λ> caminos (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) [[1,6,11,2,8,9], [1,6,11,3,8,9], [1,6,12,3,8,9], [1,7,12,3,8,9], [1,6,11,3,4,9], [1,6,12,3,4,9], [1,7,12,3,4,9], [1,6,12,8,4,9], [1,7,12,8,4,9], [1,7, 3,8,4,9]] λ> length (caminos (fromList 12 12 [1..])) 705432 |
Read More «Caminos en una matriz (con programación dinámica)»
Se considera una retícula con sus posiciones numeradas, desde el vértice superior izquierdo, hacia la derecha y hacia abajo. Por ejemplo, la retícula de dimensión 3×4 se numera como sigue:
|
1 2 3 4 5 |
|-------+-------+-------+-------| | (1,1) | (1,2) | (1,3) | (1,4) | | (2,1) | (2,2) | (2,3) | (2,4) | | (3,1) | (3,2) | (3,3) | (3,4) | |-------+-------+-------+-------| |
Definir la función
|
1 |
caminos :: (Int,Int) -> [[(Int,Int)]] |
tal que caminos (m,n) es la lista de los caminos en la retícula de dimensión mxn desde (1,1) hasta (m,n). Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
λ> caminos (2,3) [[(1,1),(1,2),(1,3),(2,3)], [(1,1),(1,2),(2,2),(2,3)], [(1,1),(2,1),(2,2),(2,3)]] λ> mapM_ print (caminos (3,4)) [(1,1),(1,2),(1,3),(1,4),(2,4),(3,4)] [(1,1),(1,2),(1,3),(2,3),(2,4),(3,4)] [(1,1),(1,2),(2,2),(2,3),(2,4),(3,4)] [(1,1),(2,1),(2,2),(2,3),(2,4),(3,4)] [(1,1),(1,2),(1,3),(2,3),(3,3),(3,4)] [(1,1),(1,2),(2,2),(2,3),(3,3),(3,4)] [(1,1),(2,1),(2,2),(2,3),(3,3),(3,4)] [(1,1),(1,2),(2,2),(3,2),(3,3),(3,4)] [(1,1),(2,1),(2,2),(3,2),(3,3),(3,4)] [(1,1),(2,1),(3,1),(3,2),(3,3),(3,4)] |
Read More «Caminos en una retícula (con programación dinámica)»
La distancia de Levenshtein (o distancia de edición) es el mínimo de operaciones requeridas para transformar una cadena de caracteres en otra. Las operaciones de edición que se pueden hacer son:
Por ejemplo, la distancia de Levenshtein entre «casa» y «calle» es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro:
|
1 2 3 |
"casa" --> "cala" (sustitución de 's' por 'l') "cala" --> "calla" (inserción de 'l' entre 'l' y 'a') "calla" --> "calle" (sustitución de 'a' por 'e') |
Definir la función
|
1 |
levenshtein :: String -> String -> Int |
tal que levenshtein xs ys es la distancia de Levenshtein entre xs e ys. Por ejemplo,
|
1 2 3 4 5 |
levenshtein "casa" "calle" == 3 levenshtein "calle" "casa" == 3 levenshtein "casa" "casa" == 0 levenshtein "ana" "maria" == 3 levenshtein "agua" "manantial" == 7 |
Read More «La distancia Levenshtein (con programación dinámica)»
Si a una secuencia X de elementos (pongamos por ejemplo, le quitamos algunos de ellos y dejamos los que quedan en el orden en el que aparecían originalmente tenemos lo que se llama una subsecuencia de X. Por ejemplo, «aaoa» es una subsecuencia de la secuencia «amapola».
El término también se aplica cuando quitamos todos los elementos (es decir, la secuencia vacía es siempre subsecuencia de cualquier secuencia) o cuando no quitamos ninguno (lo que significa que cualquier secuencia es siempre subsecuencia de sí misma).
Dadas dos secuencias X e Y, decimos que Z es una subsecuencia de X e Y si Z es subsecuencia de X y de Y. Por ejemplo, si X = «amapola» e Y = «matamoscas», la secuencia «aaoa» es una de las subsecuencias comunes de X e Y más larga, con longitud 4, ya que no hay ninguna subsecuencia común a X e Y de longitud mayor que 4. También son subsecuencias comunes de longitud 4 «maoa» o «amoa».
Definir la función
|
1 |
scm :: Eq a => [a] -> [a] -> [a] |
tal que scm xs ys es una de las subsecuencias comunes de longitud máxima de xs e ys. Por ejemplo,
|
1 2 3 |
scm "amapola" "matamoscas" == "amoa" scm "atamos" "matamoscas" == "atamos" scm "aaa" "bbbb" == "" |
Read More «Subsecuencia común máxima (con programación dinámica)»
Si a una secuencia X de elementos (pongamos por ejemplo, caracteres) le quitamos algunos de ellos y dejamos los que quedan en el orden en el que aparecían originalmente tenemos lo que se llama una subsecuencia de X. Por ejemplo, «aaoa» es una subsecuencia de la secuencia «amapola».
El término también se aplica cuando quitamos todos los elementos (es decir, la secuencia vacía es siempre subsecuencia de cualquier secuencia) o cuando no quitamos ninguno (lo que significa que cualquier secuencia es siempre subsecuencia de sí misma).
Dadas dos secuencias X e Y, decimos que Z es una subsecuencia común de X e Y si Z es subsecuencia de X y de Y. Por ejemplo, si X = «amapola» e Y = «matamoscas», la secuencia «aaoa» es una de las subsecuencias comunes de X e Y más larga, con longitud 4, ya que no hay ninguna subsecuencia común a X e Y de longitud mayor que 4. También son subsecuencias comunes de longitud 4 «maoa» o «amoa».
Se desea encontrar la longitud de las subsecuencias comunes más largas de dos secuencias de caracteres dadas.
Definir la función
|
1 |
longitudSCM :: Eq a => [a] -> [a] -> Int |
tal que longitudSCM xs ys es la longitud de la subsecuencia máxima de xs e ys. Por ejemplo,
|
1 2 3 |
longitudSCM "amapola" "matamoscas" == 4 longitudSCM "atamos" "matamoscas" == 6 longitudSCM "aaa" "bbbb" == 0 |
Read More «Longitud de la subsecuencia común máxima (con programación dinámica)»
El coeficiente binomial n sobre k es el número de subconjuntos de k elementos escogidos de un conjunto con n elementos.
Definir la función
|
1 |
binomial :: Integer -> Integer -> Integer |
tal que binomial n k es el coeficiente binomial n sobre k. Por ejemplo,
|
1 2 3 |
binomial 6 3 == 20 binomial 5 2 == 10 binomial 5 3 == 10 |
Read More «Coeficientes binomiales (con programación dinámica)»
Los primeros términos de la sucesión de Fibonacci son
|
1 |
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ... |
Escribir dos definiciones (una recursiva y otra con programación dinámica) de la función
|
1 |
fib :: Integer -> Integer |
tal que fib n es el n-ésimo término de la sucesión de Fibonacci. Por ejemplo,
|
1 |
fib 6 == 8 |
Comparar la eficiencia de las dos definiciones.
Read More «La función de Fibonacci por programación dinámica»
En el problema de las jarras (A,B,C) se tienen dos jarras sin marcas de medición, una de A litros de capacidad y otra de B. También se dispone de una bomba que permite llenar las jarras de agua.
El problema de las jarras (A,B,C) consiste en determinar cómo se puede lograr tener exactamente C litros de agua en la jarra de A litros de capacidad.
Usando el procedimiento de búsqueda en anchura, definir la función
|
1 |
jarras :: (Int,Int,Int) -> [[(Int,Int)]] |
tal jarras (a,b,c) es la lista de las soluciones del problema de las jarras (a,b,c). Por ejemplo,
|
1 2 3 4 |
λ> take 3 (jarras (4,3,2)) [[(0,0),(0,3),(3,0),(3,3),(4,2),(0,2),(2,0)], [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)], [(0,0),(0,3),(3,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)]] |
La interpretación [(0,0),(4,0),(1,3),(1,0),(0,1),(4,1),(2,3)] es:
Otros ejemplos
|
1 2 3 4 5 6 |
λ> length (jarras (15,10,5)) 8 λ> map length (jarras (15,10,5)) [3,5,5,7,7,7,8,9] λ> jarras (15,10,4) [] |
Read More «Problema de las jarras (con espacios de estados)»
El problema de suma cero consiste en, dado el conjunto de enteros, encontrar sus subconjuntos no vacío cuyos elementos sumen cero.
Usando el procedimiento de búsqueda en profundidad, definir la función
|
1 |
suma0 :: [Int] -> [[Int]] |
tal que suma0 ns es la lista de las soluciones del problema de suma cero para ns. Por ejemplo,
|
1 2 3 4 5 6 |
λ> suma0 [-7,-3,-2,5,8] [[-3,-2,5]] λ> suma0 [-7,-3,-2,5,8,-1] [[-7,-3,-2,-1,5,8],[-7,-1,8],[-3,-2,5]] λ> suma0 [-7,-3,1,5,8] [] |
Las fichas del dominó se pueden representar por pares de enteros. El problema del dominó consiste en colocar todas las fichas de una lista dada de forma que el segundo número de cada ficha coincida con el primero de la siguiente.
Usando el procedimiento de búsqueda en profundidad, definir la función
|
1 |
domino :: [(Int,Int)] -> [[(Int,Int)]] |
tal que domino fs es la lista de las soluciones del problema del dominó correspondiente a las fichas fs. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
λ> domino [(1,2),(2,3),(1,4)] [[(4,1),(1,2),(2,3)],[(3,2),(2,1),(1,4)]] λ> domino [(1,2),(1,1),(1,4)] [[(4,1),(1,1),(1,2)],[(2,1),(1,1),(1,4)]] λ> domino [(1,2),(3,4),(2,3)] [[(1,2),(2,3),(3,4)],[(4,3),(3,2),(2,1)]] λ> domino [(1,2),(2,3),(5,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 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
module El_problema_del_domino where import BusquedaEnProfundidad (buscaProfundidad) import Data.List (delete) import Test.Hspec (Spec, hspec, it, shouldBe) -- Las fichas son pares de números enteros. type Ficha = (Int,Int) -- Un problema está definido por la lista de fichas que hay que colocar type Problema = [Ficha] -- Los estados son los pares formados por la listas sin colocar y las -- colocadas. type Estado = ([Ficha],[Ficha]) -- (inicial p) es el estado inicial del problema p. Por ejemplo, -- λ> inicial [(1,2),(2,3),(1,4)] -- ([(1,2),(2,3),(1,4)],[]) inicial :: Problema -> Estado inicial p = (p,[]) -- (esFinal e) se verifica si e es un estado final. Por ejemplo, -- λ> esFinal ([], [(4,1),(1,2),(2,3)]) -- True -- λ> esFinal ([(2,3)], [(4,1),(1,2)]) -- False esFinal :: Estado -> Bool esFinal = null . fst -- (sucesores e) es la lista de los sucesores del estado e. Por ejemplo, -- λ> sucesores ([(1,2),(2,3),(1,4)],[]) -- [([(2,3),(1,4)],[(1,2)]), -- ([(1,2),(1,4)],[(2,3)]), -- ([(1,2),(2,3)],[(1,4)]), -- ([(2,3),(1,4)],[(2,1)]), -- ([(1,2),(1,4)],[(3,2)]), -- ([(1,2),(2,3)],[(4,1)])] -- λ> sucesores ([(2,3),(1,4)],[(1,2)]) -- [([(2,3)],[(4,1),(1,2)])] -- λ> sucesores ([(2,3),(1,4)],[(2,1)]) -- [([(1,4)],[(3,2),(2,1)])] sucesores :: Estado -> [Estado] sucesores (fs,[]) = [(delete (a,b) fs, [(a,b)]) | (a,b) <- fs, a /= b] ++ [(delete (a,b) fs, [(b,a)]) | (a,b) <- fs] sucesores (fs,e@((x,_):_)) = [(delete (u,v) fs,(u,v):e) | (u,v) <- fs, u /= v, v == x] ++ [(delete (u,v) fs,(v,u):e) | (u,v) <- fs, u /= v, u == x] ++ [(delete (u,v) fs,(u,v):e) | (u,v) <- fs, u == v, u == x] -- (soluciones p) es la lista de las soluciones del problema p. Por -- ejemplo, -- λ> soluciones [(1,2),(2,3),(1,4)] -- [([],[(4,1),(1,2),(2,3)]),([],[(3,2),(2,1),(1,4)])] soluciones :: Problema -> [Estado] soluciones p = buscaProfundidad sucesores esFinal (inicial p) domino :: Problema -> [[Ficha]] domino p = map snd (soluciones p) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ domino [(1,2),(2,3),(1,4)] `shouldBe` [[(4,1),(1,2),(2,3)],[(3,2),(2,1),(1,4)]] it "e2" $ domino [(1,2),(1,1),(1,4)] `shouldBe` [[(4,1),(1,1),(1,2)],[(2,1),(1,1),(1,4)]] it "e3" $ domino [(1,2),(3,4),(2,3)] `shouldBe` [[(1,2),(2,3),(3,4)],[(4,3),(3,2),(2,1)]] it "e4" $ domino [(1,2),(2,3),(5,4)] `shouldBe` [] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- -- Finished in 0.0013 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 |
from src.BusquedaEnProfundidad import buscaProfundidad # Las fichas son pares de números enteros. Ficha = tuple[int, int] # Un problema está definido por la lista de fichas que hay que colocar Problema = list[Ficha] # Los estados son los pares formados por la listas sin colocar y las # colocadas. Estado = tuple[list[Ficha], list[Ficha]] # inicial(p) es el estado inicial del problema p. Por ejemplo, # >>> inicial([(1,2),(2,3),(1,4)]) # ([(1, 2), (2, 3), (1, 4)], []) def inicial(p: Problema) -> Estado: return (p, []) # esFinal(e) se verifica si e es un estado final. Por ejemplo, # >>> esFinal(([], [(4,1),(1,2),(2,3)])) # True # >>> esFinal(([(2,3)], [(4,1),(1,2)])) # False def esFinal(e: Estado) -> bool: return not e[0] # elimina(f, fs) es la lista obtenida eliminando la ficha f de la lista # fs. Por ejemplo, # >>> elimina((1,2),[(4,1),(1,2),(2,3)]) # [(4, 1), (2, 3)] def elimina(f: Ficha, fs: list[Ficha]) -> list[Ficha]: return [g for g in fs if g != f] # sucesores(e) es la lista de los sucesores del estado e. Por ejemplo, # >>> sucesores(([(1,2),(2,3),(1,4)],[])) # [([(2,3),(1,4)],[(1,2)]), # ([(1,2),(1,4)],[(2,3)]), # ([(1,2),(2,3)],[(1,4)]), # ([(2,3),(1,4)],[(2,1)]), # ([(1,2),(1,4)],[(3,2)]), # ([(1,2),(2,3)],[(4,1)])] # >>> sucesores(([(2,3),(1,4)],[(1,2)])) # [([(2,3)],[(4,1),(1,2)])] # >>> sucesores(([(2,3),(1,4)],[(2,1)])) # [([(1,4)],[(3,2),(2,1)])] def sucesores(e: Estado) -> list[Estado]: if not e[1]: return [(elimina((a,b), e[0]), [(a,b)]) for (a,b) in e[0] if a != b] + \ [(elimina((a,b), e[0]), [(b,a)]) for (a,b) in e[0]] return [(elimina((u,v),e[0]),[(u,v)]+e[1]) for (u,v) in e[0] if u != v and v == e[1][0][0]] +\ [(elimina((u,v),e[0]),[(v,u)]+e[1]) for (u,v) in e[0] if u != v and u == e[1][0][0]] +\ [(elimina((u,v),e[0]),[(u,v)]+e[1]) for (u,v) in e[0] if u == v and u == e[1][0][0]] # soluciones(p) es la lista de las soluciones del problema p. Por # ejemplo, # >>> soluciones([(1,2),(2,3),(1,4)]) # [([], [(3, 2), (2, 1), (1, 4)]), ([], [(4, 1), (1, 2), (2, 3)])] def soluciones(p: Problema) -> list[Estado]: return buscaProfundidad(sucesores, esFinal, inicial(p)) def domino(p: Problema) -> list[list[Ficha]]: return [s[1] for s in soluciones(p)] # # Verificación # # ============ def test_domino() -> None: assert domino([(1,2),(2,3),(1,4)]) == \ [[(3, 2), (2, 1), (1, 4)], [(4, 1), (1, 2), (2, 3)]] assert domino([(1,2),(1,1),(1,4)]) == \ [[(2, 1), (1, 1), (1, 4)], [(4, 1), (1, 1), (1, 2)]] assert domino([(1,2),(3,4),(2,3)]) == \ [[(4, 3), (3, 2), (2, 1)], [(1, 2), (2, 3), (3, 4)]] assert domino([(1,2),(2,3),(5,4)]) == \ [] print("Verificado") # La verificación es # >>> test_domino() # Verificado |
El problema del calendario, para una competición deportiva en la que se enfrentan n participantes, consiste en elaborar un calendario de forma que:
Por ejemplo, con 8 participantes una posible solución es
|
1 2 3 4 5 6 7 8 9 10 |
| 1 2 3 4 5 6 7 --+-------------- 1 | 2 3 4 5 6 7 8 2 | 1 4 3 6 5 8 7 3 | 4 1 2 7 8 5 6 4 | 3 2 1 8 7 6 5 5 | 6 7 8 1 2 3 4 6 | 5 8 7 2 1 4 3 7 | 8 5 6 3 4 1 2 8 | 7 6 5 4 3 2 1 |
donde las filas indican los jugadores y las columnas los días; es decir, el elemento (i,j) indica el adversario del jugador i el día j; por ejemplo, el adversario del jugador 2 el 4ª día es el jugador 6.
Para representar el problema se define el tipo Calendario como matrices de enteros,
Usando el procedimiento de búsqueda en profundidad, definir la función
|
1 |
calendario :: Int -> [Calendario] |
tal que calendario n son las soluciones del problema del calendario, con n participantes, mediante el patrón de búsqueda em profundidad. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
λ> head (calendario 6) ┌ ┐ │ 2 3 4 5 6 │ │ 1 4 5 6 3 │ │ 5 1 6 4 2 │ │ 6 2 1 3 5 │ │ 3 6 2 1 4 │ │ 4 5 3 2 1 │ └ ┘ λ> length (calendario 6) 720 λ> length (calendario 5) 0 |
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 |
module El_problema_del_calendario_mediante_busqueda_en_espacio_de_estado where import BusquedaEnProfundidad (buscaProfundidad) import Data.Matrix (Matrix, (!), nrows, zero, setElem, toLists) import Data.List ((\\)) import Test.Hspec (Spec, hspec, it, shouldBe) type Calendario = Matrix Int -- (inicial n) es el estado inicial para el problema del calendario con -- n participantes; es decir, una matriz de n fila y n-1 columnas con -- todos sus elementos iguales a 0. Por ejemplo, -- λ> inicial 4 -- ┌ ┐ -- │ 0 0 0 │ -- │ 0 0 0 │ -- │ 0 0 0 │ -- │ 0 0 0 │ -- └ ┘ inicial :: Int -> Calendario inicial n = zero n (n-1) -- (huecos c) es la lista de las posiciones de c cuyo valor es 0. huecos :: Calendario -> [(Int, Int)] huecos c = [(i,j) | i <- [1..n], j <- [1..n-1], c!(i,j) == 0] where n = nrows c -- (sucesores c) es la lista de calendarios obtenidos poniendo en el -- lugar del primer elemento nulo de c uno de los posibles jugadores de -- forma que se cumplan las condiciones del problema. Por ejemplo, -- λ> sucesores (inicial 4) -- [┌ ┐ ┌ ┐ ┌ ┐ -- │ 2 0 0 │ │ 3 0 0 │ │ 4 0 0 │ -- │ 1 0 0 │ │ 0 0 0 │ │ 0 0 0 │ -- │ 0 0 0 │ │ 1 0 0 │ │ 0 0 0 │ -- │ 0 0 0 │ │ 0 0 0 │ │ 1 0 0 │ -- └ ┘, └ ┘, └ ┘] -- λ> sucesores (fromLists [[2,3,0],[1,0,0],[0,1,0],[0,0,0]]) -- [┌ ┐ -- │ 2 3 4 │ -- │ 1 0 0 │ -- │ 0 1 0 │ -- │ 0 0 1 │ -- └ ┘] -- λ> sucesores (fromLists [[2,3,4],[1,0,0],[0,1,0],[0,0,1]]) -- [┌ ┐ -- │ 2 3 4 │ -- │ 1 4 0 │ -- │ 0 1 0 │ -- │ 0 2 1 │ -- └ ┘] sucesores :: Calendario -> [Calendario] sucesores c = [setElem i (k,j) (setElem k (i,j) c) | k <- [1..n] \\ (i : [c!(k,j) | k <- [1..i-1]] ++ [c!(i,k) | k <- [1..j-1]]), c!(k,j) == 0] where n = nrows c (i,j) = head (huecos c) -- (esFinal c) se verifica si c un estado final para el problema -- del calendario con n participantes; es decir, no queda en c ningún -- elemento igual a 0. Por ejemplo, -- λ> esFinal (fromLists [[2,3,4],[1,4,3],[4,1,2],[3,2,1]]) -- True -- λ> esFinal (fromLists [[2,3,4],[1,4,3],[4,1,2],[3,2,0]]) -- False esFinal :: Calendario -> Bool esFinal c = null (huecos c) calendario :: Int -> [Calendario] calendario n = buscaProfundidad sucesores esFinal (inicial n) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ toLists (head (calendario 6)) `shouldBe` [[2,3,4,5,6],[1,4,5,6,3],[5,1,6,4,2],[6,2,1,3,5],[3,6,2,1,4],[4,5,3,2,1]] it "e2" $ length (calendario 6) `shouldBe` 720 it "e3" $ length (calendario 5) `shouldBe` 0 -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- -- Finished in 0.2580 seconds -- 3 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 |
from copy import deepcopy from typing import Optional import numpy as np import numpy.typing as npt from src.BusquedaEnProfundidad import buscaProfundidad Calendario = npt.NDArray[np.complex64] # inicial(n) es el estado inicial para el problema del calendario con # n participantes; es decir, una matriz de n fila y n-1 columnas con # todos sus elementos iguales a 0. Por ejemplo, # >>> inicial(4) # array([[0, 0, 0], # [0, 0, 0], # [0, 0, 0], # [0, 0, 0]]) def inicial(n: int) -> Calendario: return np.zeros((n, n - 1), dtype=int) # primerHueco(c) es la posición del primer elemento cuyo valor es 0. Si # todos los valores son distintos de 0, devuelve (-1,-1). Por ejemplo, # primerHueco(np.array([[1,2,3],[4,5,0],[7,0,0]])) == (1, 2) # primerHueco(np.array([[1,2,3],[4,5,6],[7,8,0]])) == (2, 2) # primerHueco(np.array([[1,2,3],[4,5,6],[7,8,9]])) == (-1, -1) def primerHueco(c: Calendario) -> tuple[int, int]: (n, m) = c.shape for i in range(0, n): for j in range(0, m): if c[i,j] == 0: return (i, j) return (-1, -1) # libres(c, i, j) es la lista de valores que que pueden poner en la # posición (i,j) del calendario c. Por ejemplo, # libres(np.array([[0,0,0],[0,0,0],[0,0,0],[0,0,0]]),0,0) == [2, 3, 4] # libres(np.array([[2,0,0],[1,0,0],[0,0,0],[0,0,0]]),0,1) == [3, 4] # libres(np.array([[2,3,0],[1,0,0],[0,1,0],[0,0,0]]),0,2) == [4] # libres(np.array([[2,3,4],[1,0,0],[0,1,0],[0,0,1]]),1,1) == [4] # libres(np.array([[2,3,4],[1,4,0],[0,1,0],[0,2,1]]),1,2) == [3] def libres(c: Calendario, i: int, j: int) -> list[int]: n = c.shape[0] return list(set(range(1, n + 1)) - {i + 1} - set(c[i]) - set(c[:,j])) # setElem(k, i, j, c) es el calendario obtenido colocando en c el valor # k en la posición (i,j). # >>> setElem(7,1,2,np.array([[1,2,3],[4,5,0],[0,0,0]])) # array([[1, 2, 3], # [4, 5, 7], # [0, 0, 0]]) def setElem(k: int, i: int, j: int, c: Calendario) -> Calendario: _c = deepcopy(c) _c[i, j] = k return _c # sucesores(c) es la lista de calendarios obtenidos poniendo en el # lugar del primer elemento nulo de c uno de los posibles jugadores de # forma que se cumplan las condiciones del problema. Por ejemplo, # >>> sucesores(np.array([[0,0,0],[0,0,0],[0,0,0],[0,0,0]])) # [array([[2,0,0], [1,0,0], [0,0,0], [0,0,0]]), # array([[3,0,0], [0,0,0], [1,0,0], [0,0,0]]), # array([[4,0,0], [0,0,0], [0,0,0], [1,0,0]])] # >>> sucesores(np.array([[2,0,0],[1,0,0],[0,0,0],[0,0,0]])) # [array([[2,3,0], [1,0,0], [0,1,0], [0,0,0]]), # array([[2,4,0], [1,0,0], [0,0,0], [0,1,0]])] # >>> sucesores(np.array([[2,3,0],[1,0,0],[0,1,0],[0,0,0]])) # [array([[2,3,4], [1,0,0], [0,1,0], [0,0,1]])] # >>> sucesores(np.array([[2,3,4],[1,0,0],[0,1,0],[0,0,1]])) # [array([[2,3,4], [1,4,0], [0,1,0], [0,2,1]])] # >>> sucesores(np.array([[2,3,4],[1,4,0],[0,1,0],[0,2,1]])) # [array([[2,3,4], [1,4,3], [0,1,2], [0,2,1]])] # >>> sucesores(np.array([[2,3,4],[1,4,3],[0,1,2],[0,2,1]])) # [array([[2,3,4], [1,4,3], [4,1,2], [3,2,1]])] # >>> sucesores(np.array([[2,3,4],[1,4,3],[4,1,2],[3,2,1]])) # [] def sucesores(c: Calendario) -> list[Calendario]: n = c.shape[0] (i, j) = primerHueco(c) return [setElem(i+1, k-1, j, setElem(k, i, j, c)) for k in libres(c, i, j)] # esFinal(c) se verifica si c un estado final para el problema # del calendario con n participantes; es decir, no queda en c ningún # elemento igual a 0. Por ejemplo, # >>> esFinal(np.array([[2,3,4],[1,4,3],[4,1,2],[3,2,1]])) # True # >>> esFinal(np.array([[2,3,4],[1,4,3],[4,1,2],[3,2,0]])) # False def esFinal(c: Calendario) -> bool: return primerHueco(c) == (-1, -1) def calendario(n: int) -> list[Calendario]: return buscaProfundidad(sucesores, esFinal, inicial(n)) # Verificación # ============ def test_calendario() -> None: def filas(p: Calendario) -> list[list[int]]: return p.tolist() assert filas(calendario(6)[0]) == \ [[6, 5, 4, 3, 2], [5, 4, 3, 6, 1], [4, 6, 2, 1, 5], [3, 2, 1, 5, 6], [2, 1, 6, 4, 3], [1, 3, 5, 2, 4]] assert len(calendario(6)) == 720 assert len(calendario(5)) == 0 print("Verificado") |
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:
Ficha con tres constructores B, V y H que representan las fichas blanca, verde y hueco, respectivamente.|
1 2 |
data Ficha = B | V | H deriving (Eq, Show) |
Tablero que es una lista de fichas que representa las fichas colocadas en el tablero.|
1 |
type Tablero = [Ficha] |
Estado representa 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) |
Busqueda es 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 |
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:
Orilla con dos constructores (I y D) que representan las orillas izquierda y derecha, respectivamente.Estado que 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 |
El algoritmo de Prim calcula un recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de todas las aristas del árbol es el mínimo.
El algoritmo de Prim funciona de la siguiente manera:
Usando la búsqueda en escalada el tipo abstracto de datos de los grafos, definir la función
|
1 |
prim :: (Ix v, Num p, Ord p) => Grafo v p -> [(p,v,v)] |
tal que prim g es el árbol de expansión mínimo del grafo g calculado mediante el algoritmo de Prim con bñusqueda en escalada. Por ejemplo, si g1, g2, g3 y g4 son los grafos definidos por
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
g1, g2, g3, g4 :: Grafo Int Int g1 = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)] g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78), (2,4,12),(2,5,32), (3,4,14),(3,5,44), (4,5,93)] g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,7), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,1), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] |
entonces
|
1 2 3 4 |
prim g1 == [(2,4,55),(1,3,34),(2,5,32),(1,2,12)] prim g2 == [(2,5,32),(2,4,12),(1,2,13),(1,3,11)] prim g3 == [(5,7,9),(2,3,7),(5,4,5),(6,5,3),(1,6,6),(1,2,5)] prim g4 == [(5,7,9),(5,4,5),(5,3,1),(6,5,3),(1,6,6),(1,2,5)] |
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 |
module Escalada_Prim where import BusquedaEnEscalada (buscaEscalada) import TAD.Grafo (Grafo, Orientacion (ND), aristaEn, creaGrafo, nodos, peso) import Data.Ix (Ix) import Data.List (delete) import Test.Hspec (Spec, hspec, it, shouldBe) g1, g2, g3, g4 :: Grafo Int Int g1 = creaGrafo ND (1,5) [(1,2,12),(1,3,34),(1,5,78), (2,4,55),(2,5,32), (3,4,61),(3,5,44), (4,5,93)] g2 = creaGrafo ND (1,5) [(1,2,13),(1,3,11),(1,5,78), (2,4,12),(2,5,32), (3,4,14),(3,5,44), (4,5,93)] g3 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,7), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] g4 = creaGrafo ND (1,7) [(1,2,5),(1,3,9),(1,5,15),(1,6,6), (2,3,7), (3,4,8),(3,5,1), (4,5,5), (5,6,3),(5,7,9), (6,7,11)] -- Una arista esta formada por dos vértices junto con su peso. type Arista a b = (a,a,b) -- Un estado (Estado (p,t,r,aem)) está formado por el peso p de la -- última arista añadida el árbol de expansión mínimo (aem), la lista t -- de nodos del grafo que están en el aem, la lista r de nodos del -- grafo que no están en el aem y el aem. type Estado a b = (b,[a],[a],[Arista a b]) -- (inicial g) es el estado inicial correspondiente al grafo g. inicial :: (Ix a, Num b, Ord b) => Grafo a b -> Estado a b inicial g = (0,[n],ns,[]) where (n:ns) = nodos g -- (esFinal e) se verifica si e es un estado final; es decir, si no -- queda ningún elemento en la lista de nodos sin colocar en el árbol de -- expansión mínimo. esFinal :: Estado a b -> Bool esFinal (_,_,[],_) = True esFinal _ = False -- (sucesores g e) es la lista de los sucesores del estado e en el -- grafo g. Por ejemplo, -- λ> sucesores g1 (0,[1],[2..5],[]) -- [(12,[2,1],[3,4,5],[(1,2,12)]), -- (34,[3,1],[2,4,5],[(1,3,34)]), -- (78,[5,1],[2,3,4],[(1,5,78)])] sucesores :: (Ix a, Num b, Eq b) => Grafo a b -> Estado a b -> [Estado a b] sucesores g (_,t,r,aem) = [(peso x y g, y:t, delete y r, (x,y,peso x y g):aem) | x <- t , y <- r, aristaEn g (x,y)] prim :: (Ix a, Num b, Ord b) => Grafo a b -> [Arista a b] prim g = sol where [(_,_,_,sol)] = buscaEscalada (sucesores g) esFinal (inicial g) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ prim g1 `shouldBe` [(2,4,55),(1,3,34),(2,5,32),(1,2,12)] it "e2" $ prim g2 `shouldBe` [(2,5,32),(2,4,12),(1,2,13),(1,3,11)] it "e3" $ prim g3 `shouldBe` [(5,7,9),(2,3,7),(5,4,5),(6,5,3),(1,6,6),(1,2,5)] it "e4" $ prim g4 `shouldBe` [(5,7,9),(5,4,5),(5,3,1),(6,5,3),(1,6,6),(1,2,5)] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- -- Finished in 0.0043 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 |
from typing import Optional from src.BusquedaEnEscalada import buscaEscalada from src.TAD.Grafo import (Grafo, Orientacion, Peso, Vertice, aristaEn, creaGrafo, nodos, peso) g1 = creaGrafo (Orientacion.ND, (1,5), [((1,2),12),((1,3),34),((1,5),78), ((2,4),55),((2,5),32), ((3,4),61),((3,5),44), ((4,5),93)]) g2 = creaGrafo (Orientacion.ND, (1,5), [((1,2),13),((1,3),11),((1,5),78), ((2,4),12),((2,5),32), ((3,4),14),((3,5),44), ((4,5),93)]) g3 = creaGrafo (Orientacion.ND, (1,7), [((1,2),5),((1,3),9),((1,5),15),((1,6),6), ((2,3),7), ((3,4),8),((3,5),7), ((4,5),5), ((5,6),3),((5,7),9), ((6,7),11)]) g4 = creaGrafo (Orientacion.ND, (1,7), [((1,2),5),((1,3),9),((1,5),15),((1,6),6), ((2,3),7), ((3,4),8),((3,5),1), ((4,5),5), ((5,6),3),((5,7),9), ((6,7),11)]) Arista = tuple[tuple[Vertice, Vertice], Peso] # Un nodo (Estado (p,t,r,aem)) está formado por el peso p de la última # arista añadida el árbol de expansión mínimo (aem), la lista t # de nodos del grafo que están en el aem, la lista r de nodos del # grafo que no están en el aem y el aem. Estado = tuple[Peso, list[Vertice], list[Vertice], list[Arista]] # inicial(g) es el estado inicial correspondiente al grafo g. def inicial(g: Grafo) -> Estado: n, *ns = nodos(g) return (0, [n], ns, []) # esFinal(e) se verifica si e es un estado final; es decir, si no # queda ningún elemento en la lista de nodos sin colocar en el árbol de # expansión mínimo. def esFinal(e: Estado) -> bool: return e[2] == [] # sucesores(g, e) es la lista de los sucesores del estado e en el # grafo g. Por ejemplo, # λ> sucesores(g1, (0,[1],[2,3,4,5],[])) # [(12,[2,1],[3,4,5],[(1,2,12)]), # (34,[3,1],[2,4,5],[(1,3,34)]), # (78,[5,1],[2,3,4],[(1,5,78)])] def sucesores(g: Grafo, e: Estado) -> list[Estado]: (_,t,r,aem) = e return [(peso(x, y, g), [y] + t, [x for x in r if x != y], [((x,y),peso(x, y, g))] + aem) for x in t for y in r if aristaEn(g, (x, y))] def prim(g: Grafo) -> Optional[list[Arista]]: r = buscaEscalada(lambda e: sucesores(g, e), esFinal, inicial(g)) if r is None: return None return r[3] # Verificación # ============ def test_prim() -> None: assert prim(g1) == [((2,4),55),((1,3),34),((2,5),32),((1,2),12)] assert prim(g2) == [((2,5),32),((2,4),12),((1,2),13),((1,3),11)] assert prim(g3) == [((5,7),9),((2,3),7),((5,4),5),((6,5),3),((1,6),6),((1,2),5)] assert prim(g4) == [((5,7),9),((5,4),5),((5,3),1),((6,5),3),((1,6),6),((1,2),5)] print("Verificado") # La verificación es # >>> test_prim() # Verificado |
El problema del cambio de monedas consiste en determinar conseguir una cantidad usando el menor número de monedas disponibles. Se supone que se posee un número ilimitado de monedas de 1, 2, 5, 10, 20, 50 y 100 euros. Por ejemplo, para conseguir 199 se necesitan como mínimo 7 monedas (129 = 2 + 2 + 5 + 20 + 20 + 50 + 100).
En la representación se usarán los siguientes tipos:
Moneda, que es un número entero representado el valor de la monedaSolucion, que es una lista de monedas cuya suma es la cantidad deseada y no nay ninguna lista más corta con la misma suma.Usando la búsqueda en escalada, definir la función
|
1 |
cambio :: Int -> Solucion |
tal que (cambio n) es la solución del problema de las monedas, para obtener la cantidad n, por búsqueda en escalada. Por ejemplo,
|
1 |
cambio 199 == [2,2,5,20,20,50,100] |
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 |
module Escalada_Monedas where import BusquedaEnEscalada import Test.Hspec (Spec, hspec, it, shouldBe) -- Las monedas son números enteros. type Moneda = Int -- monedas es la lista del tipo de monedas disponibles. Se supone que -- hay un número infinito de monedas de cada tipo. monedas :: [Moneda] monedas = [1,2,5,10,20,50,100] -- Las soluciones son listas de monedas. type Solucion = [Moneda] -- Los estados son pares formados por la cantidad que falta y la lista -- de monedas usadas. type Estado = (Int, [Moneda]) -- (inicial n) es el estado inicial del problema de las monedas, para -- obtener la cantidad n. inicial :: Int -> Estado inicial n = (n, []) -- (esFinal e) se verifica si e es un estado final del problema -- de las monedas. esFinal :: Estado -> Bool esFinal (v,_) = v == 0 -- (sucesores e) es la lista de los sucesores del estado e en el -- problema de las monedas. Por ejemplo, -- λ> sucesores (199,[]) -- [(198,[1]),(197,[2]),(194,[5]),(189,[10]), -- (179,[20]),(149,[50]),(99,[100])] sucesores :: Estado -> [Estado] sucesores (r,p) = [(r-c,c:p) | c <- monedas, r-c >= 0] cambio :: Int -> Solucion cambio n = snd (head (buscaEscalada sucesores esFinal (inicial n))) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ cambio 199 `shouldBe` [2,2,5,20,20,50,100] -- La verificación es -- λ> verifica -- -- e1 -- -- Finished in 0.0003 seconds -- 1 example, 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 |
from typing import Optional from src.BusquedaEnEscalada import buscaEscalada # Las monedas son números enteros. Moneda = int # monedas es la lista del tipo de monedas disponibles. Se supone que # hay un número infinito de monedas de cada tipo. monedas: list[Moneda] = [1,2,5,10,20,50,100] # Las soluciones son listas de monedas. Solucion = list[Moneda] # Los estados son pares formados por la cantidad que falta y la lista # de monedas usadas. Estado = tuple[int, list[Moneda]] # inicial(n) es el estado inicial del problema de las monedas, para # obtener la cantidad n. def inicial(n: int) -> Estado: return (n, []) # esFinal(e) se verifica si e es un estado final del problema # de las monedas. def esFinal(e: Estado) -> bool: return e[0] == 0 # sucesores(e) es la lista de los sucesores del estado e en el # problema de las monedas. Por ejemplo, # λ> sucesores((199,[])) # [(198,[1]),(197,[2]),(194,[5]),(189,[10]), # (179,[20]),(149,[50]),(99,[100])] def sucesores(e: Estado) -> list[Estado]: (r,p) = e return [(r - c, [c] + p) for c in monedas if r - c >= 0] def cambio(n: int) -> Optional[Solucion]: r = buscaEscalada(sucesores, esFinal, inicial(n)) if r is None: return None return r[1] # Verificación # ============ def test_monedas() -> None: assert cambio(199) == [2,2,5,20,20,50,100] # La verificación es # src> poetry run pytest -q Escalada_Monedas.py # 1 passed in 0.12s |