Menu Close

El tipo abstracto de datos de las colas de prioridad

José A. Alonso, ,

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:

   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:

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:

{-# 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:

__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,

   >>> 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,

   >>> 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.

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
Leer más →

El problema de la mochila (mediante espacio de estados)

José A. Alonso, ,

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.
     type SolMoch = [Objeto]
  • Los objetos son pares formado por un peso y un valor
     type Objeto = (Peso,Valor)
  • Los pesos son número enteros
     type Peso = Int
  • Los valores son números reales.
     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.
     type NodoMoch = (Valor,Peso,Peso,[Objeto],SolMoch)

Usando el procedimiento de búsqueda en profundidad, definir la función

   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,

   > 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.


Soluciones en Haskell

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


Soluciones en Python

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
Leer más →

El problema de las n reinas (mediante búsqueda por anchura en espacios de estados)

José A. Alonso, ,

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.

   type Columna = Int
   type Fila    = Int

Una solución del problema de las n reinas es una lista de posiciones.

   type SolNR = [(Columna,Fila)]

Usando el procedimiento de búsqueda en anchura, definir las funciones

   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,
     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,
     λ> 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,
     nSolucionesNR 8  ==  92

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

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


Soluciones en Python

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
Leer más →

Búsqueda por anchura en espacios de estados

José A. Alonso, ,

Las características de los problemas de espacios de estados son:

  • un conjunto de las posibles situaciones o nodos que constituye el espacio de estados (estos son las potenciales soluciones que se necesitan explorar),
  • un conjunto de movimientos de un nodo a otros nodos, llamados los sucesores del nodo,
  • un nodo inicial y
  • un nodo objetivo que es la solución.

Definir la función

   buscaAnchura :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool)
                              -> nodo -> [nodo]

tal que buscaAnchura 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 mediante búsqueda en anchura.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

module BusquedaEnAnchura (buscaAnchura) where
 
import TAD.Cola (esVacia, inserta, primero, resto, vacia)
 
buscaAnchura :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool)
                               -> nodo -> [nodo]
buscaAnchura sucesores esFinal inicial =
  aux (inserta inicial vacia)
  where
    aux p
      | esVacia p        = []
      | esFinal (primero p) = primero p : aux (resto p)
      | otherwise        = aux (foldr
                                inserta
                                (resto p)
                                (sucesores (primero p)))


Soluciones en Python

from functools import reduce
from sys import setrecursionlimit
from typing import Callable, TypeVar
 
from src.TAD.cola import Cola, esVacia, inserta, primero, resto, vacia
 
A = TypeVar('A')
 
setrecursionlimit(10**6)
 
def buscaAnchura(sucesores: Callable[[A], list[A]],
                  esFinal: Callable[[A], bool],
                  inicial: A) -> list[A]:
    def aux(p: Cola[A]) -> list[A]:
        if esVacia(p):
            return []
        if esFinal(primero(p)):
            return [primero(p)] + aux(resto(p))
        return aux(reduce(lambda x, y: inserta(y, x),
                          sucesores(primero(p)),
                          resto(p)))
 
    return aux (inserta(inicial, vacia()))
Leer más →

El problema de las n reinas (mediante búsqueda por profundidad en espacios de estados)

José A. Alonso, ,

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.

   type Columna = Int
   type Fila    = Int

Una solución del problema de las n reinas es una lista de posiciones.

   type SolNR = [(Columna,Fila)]

Usando el procedimiento de búsqueda en profundidad, definir las funciones

   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 profundidad. Por ejemplo,
     take 3 (solucionesNR 8)
     [[(1,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4)],
      [(1,1),(2,6),(3,8),(4,3),(5,7),(6,4),(7,2),(8,5)],
      [(1,1),(2,7),(3,4),(4,6),(5,8),(6,2),(7,5),(8,3)]]
  • primeraSolucionNR n es la primera solución del problema de las n reinas, por búsqueda en espacio de estados por profundidad. Por ejemplo,
     λ> primeraSolucionNR 8
     [(1,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4)]
  • nSolucionesNR n es el número de soluciones del problema de las n reinas, por búsqueda en espacio de estados. Por ejemplo,
     nSolucionesNR 8  ==  92

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

module BEE_Reinas_Profundidad where
 
import BusquedaEnProfundidad (buscaProfundidad)
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 (buscaProfundidad 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,1),(2,5),(3,8),(4,6),(5,3),(6,7),(7,2),(8,4)],
     [(1,1),(2,6),(3,8),(4,3),(5,7),(6,4),(7,2),(8,5)],
     [(1,1),(2,7),(3,4),(4,6),(5,8),(6,2),(7,5),(8,3)]]
  it "e2" $
    nSolucionesNR 8 `shouldBe` 92
 
-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--
--    Finished in 0.1173 seconds
--    2 examples, 0 failures


Soluciones en Python

from src.BusquedaEnProfundidad import buscaProfundidad
 
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 buscaProfundidad(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(8)[:3] == \
        [[(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)]]
    assert nSolucionesNR(8) == 92
    print("Verificado")
 
# La verificación es
#    >>> test_nReinas()
#    Verificado
Leer más →