Ir al contenido principal

Búsqueda en escalada

En la búsqueda en escalada se supone que los estados están mediante una función, la heurística, que es una estimación de su coste para llegar a un estado final.

Definir la función

   buscaEscalada :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n]

tal que (buscaEscalada s o e) es la lista de soluciones del problema de espacio de estado definido por la función sucesores s, el objetivo o y estado inicial e, obtenidas buscando en escalada.

Nota: La búsqueda en escalada se aplica en el problema de las monedas.

Soluciones

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

Soluciones en Haskell

module BusquedaEnEscalada (buscaEscalada)  where

import TAD.ColaDePrioridad (esVacia, inserta, primero, vacia)

buscaEscalada :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n]
buscaEscalada sucesores esFinal x = busca' (inserta x vacia) where
  busca' c
    | esVacia c           = []
    | esFinal (primero c) = [primero c]
    | otherwise           = busca' (foldr inserta vacia (sucesores (primero c)))

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from functools import reduce
from typing import Callable, Optional, Protocol, TypeVar

from src.TAD.ColaDePrioridad import (CPrioridad, esVacia, inserta, primero,
                                     vacia)


class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

def buscaEscalada(sucesores: Callable[[A], list[A]],
                  esFinal: Callable[[A], bool],
                  inicial: A) -> Optional[A]:
    c: CPrioridad[A] = inserta(inicial, vacia())

    while not esVacia(c):
        x = primero(c)
        if esFinal(x):
            return x

        c = reduce(lambda x, y: inserta(y, x), sucesores(x), vacia())

    return None