Búsqueda en espacios de estados por profundidad
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 |
buscaProfundidad :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool) -> nodo -> [nodo] |
tal que buscaProfundidad 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 profundidad.
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 BusquedaEnProfundidad (buscaProfundidad) where import TAD.Pila (apila, cima, desapila, esVacia, vacia) buscaProfundidad :: Eq nodo => (nodo -> [nodo]) -> (nodo -> Bool) -> nodo -> [nodo] buscaProfundidad sucesores esFinal inicial = aux (apila inicial vacia) where aux p | esVacia p = [] | esFinal (cima p) = cima p : aux (desapila p) | otherwise = aux (foldr apila (desapila p) (sucesores (cima 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.pila import Pila, apila, cima, desapila, esVacia, vacia A = TypeVar('A') setrecursionlimit(10**6) def buscaProfundidad1(sucesores: Callable[[A], list[A]], esFinal: Callable[[A], bool], inicial: A) -> list[A]: def aux(p: Pila[A]) -> list[A]: if esVacia(p): return [] if esFinal(cima(p)): return [cima(p)] + aux(desapila(p)) return aux(reduce(lambda x, y: apila(y, x), sucesores(cima(p)), desapila(p))) return aux(apila(inicial, vacia())) |