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
|
1 |
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.
|
1 2 3 4 5 6 7 8 9 10 |
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))) |
|
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 |
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 |