Búsqueda por primero el mejor
En la búsqueda por primero el mejor se supone que los estados están ordenados 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 |
buscaPM :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n] |
tal que buscaPM 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 por primero el mejor.
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 BusquedaPrimeroElMejor (buscaPM) where import TAD.ColaDePrioridad (esVacia, inserta, primero, resto, vacia) buscaPM :: Ord n => (n -> [n]) -> (n -> Bool) -> n -> [n] buscaPM sucesores esFinal x = busca' (inserta x vacia) where busca' c | esVacia c = [] | esFinal (primero c) = primero c : busca' (resto c) | otherwise = busca' (foldr inserta (resto c) (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, resto, vacia) class Comparable(Protocol): @abstractmethod def __lt__(self: A, otro: A) -> bool: pass A = TypeVar('A', bound=Comparable) def buscaPM(sucesores: Callable[[A], list[A]], esFinal: Callable[[A], bool], inicial: A) -> Optional[A]: c: CPrioridad[A] = inserta(inicial, vacia()) while not esVacia(c): if esFinal(primero(c)): return primero(c) es = sucesores(primero(c)) c = reduce(lambda x, y: inserta(y, x), es, resto(c)) return None |