Búsqueda por primero el mejor

José A. Alonso

06-07-2023

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 rstimación de su coste para llegar a un estado final.

Definir la función

   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.

Soluciones en Haskell

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

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