-- |
-- Module      : BusquedaPrimeroElMejor
-- Description : El patrón de búsqueda por primero el mejor.
-- License     : Creative Commons
-- Maintainer  : José A. Alonso
-- 
-- = El patrón de búsqueda por primero el mejor
-- 
-- Este módulo contiene la definición del patrón de búsqueda por primero
-- el mejor estudiado en el <http://bit.ly/1IstIjL tema 15> del
-- curso. 
--
-- Además, en el tema se incluye como de aplicación del patrón el 
-- <http://bit.ly/1IstOI7 problema del 8-puzzle>.

module I1M.BusquedaPrimeroElMejor (buscaPM)  where

-- ---------------------------------------------------------------------
-- Importaciones                                                      --
-- ---------------------------------------------------------------------

import I1M.ColaDePrioridad

-- ---------------------------------------------------------------------
-- Búsqueda por primero el mejor                                      --
-- ---------------------------------------------------------------------

-- | (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 el
-- estado inicial (e), obtenidas buscando por primero el mejor.
buscaPM :: (Ord nodo) => 
           (nodo -> [nodo])   -- sucesores
           -> (nodo -> Bool)  -- esFinal
           -> nodo            -- nodo actual
           -> [nodo]          -- solución
buscaPM :: (nodo -> [nodo]) -> (nodo -> Bool) -> nodo -> [nodo]
buscaPM nodo -> [nodo]
sucesores nodo -> Bool
esFinal nodo
x = CPrioridad nodo -> [nodo]
busca' (nodo -> CPrioridad nodo -> CPrioridad nodo
forall a. Ord a => a -> CPrioridad a -> CPrioridad a
inserta nodo
x CPrioridad nodo
forall a. Ord a => CPrioridad a
vacia)
 where
   busca' :: CPrioridad nodo -> [nodo]
busca' CPrioridad nodo
c 
     | CPrioridad nodo -> Bool
forall a. Ord a => CPrioridad a -> Bool
esVacia CPrioridad nodo
c = []
     | nodo -> Bool
esFinal (CPrioridad nodo -> nodo
forall a. Ord a => CPrioridad a -> a
primero CPrioridad nodo
c)  = CPrioridad nodo -> nodo
forall a. Ord a => CPrioridad a -> a
primero CPrioridad nodo
c nodo -> [nodo] -> [nodo]
forall a. a -> [a] -> [a]
: CPrioridad nodo -> [nodo]
busca' (CPrioridad nodo -> CPrioridad nodo
forall a. Ord a => CPrioridad a -> CPrioridad a
resto CPrioridad nodo
c)
     | Bool
otherwise = CPrioridad nodo -> [nodo]
busca' ((nodo -> CPrioridad nodo -> CPrioridad nodo)
-> CPrioridad nodo -> [nodo] -> CPrioridad nodo
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr nodo -> CPrioridad nodo -> CPrioridad nodo
forall a. Ord a => a -> CPrioridad a -> CPrioridad a
inserta (CPrioridad nodo -> CPrioridad nodo
forall a. Ord a => CPrioridad a -> CPrioridad a
resto CPrioridad nodo
c) (nodo -> [nodo]
sucesores (CPrioridad nodo -> nodo
forall a. Ord a => CPrioridad a -> a
primero CPrioridad nodo
c)))