Búsqueda por anchura en espacios de estados
Las características de los problemas de espacios de estados son:
- un conjunto de las posibles situaciones o nodos que constituye el espacio de estados (estos son las potenciales soluciones que se necesitan explorar),
- un conjunto de movimientos de un nodo a otros nodos, llamados los sucesores del nodo,
- un nodo inicial y
- un nodo objetivo que es la solución.
Definir la función
1 2 |
buscaAnchura :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool) -> nodo -> [nodo] |
tal que buscaAnchura 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 mediante búsqueda en anchura.
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 11 12 13 14 15 16 |
module BusquedaEnAnchura (buscaAnchura) where import TAD.Cola (esVacia, inserta, primero, resto, vacia) buscaAnchura :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool) -> nodo -> [nodo] buscaAnchura sucesores esFinal inicial = aux (inserta inicial vacia) where aux p | esVacia p = [] | esFinal (primero p) = primero p : aux (resto p) | otherwise = aux (foldr inserta (resto p) (sucesores (primero p))) |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
from functools import reduce from sys import setrecursionlimit from typing import Callable, TypeVar from src.TAD.cola import Cola, esVacia, inserta, primero, resto, vacia A = TypeVar('A') setrecursionlimit(10**6) def buscaAnchura(sucesores: Callable[[A], list[A]], esFinal: Callable[[A], bool], inicial: A) -> list[A]: def aux(p: Cola[A]) -> list[A]: if esVacia(p): return [] if esFinal(primero(p)): return [primero(p)] + aux(resto(p)) return aux(reduce(lambda x, y: inserta(y, x), sucesores(primero(p)), resto(p))) return aux (inserta(inicial, vacia())) |