23. El algoritmo de profundidad iterada
El algoritmo de profundidad iterada. En inglés se le conoce como "iterative deepening", lo vamos a abreviar ID. El algoritmo ID tiene dos entradas: la primera es el estado inicial y la segunda es la función de paro. El algoritmo realmente es muy simple. Vamos a requerir de un contador, llamémosle "i", el cual vamos a inicializar con un valor de uno. La solución, vamos a considerar que no la tenemos y la vamos a inicializar como "no existente". Después, vamos a entrar en un ciclo mientras la solución no se encuentre.
Entonces, invocamos el algoritmo DLS. Le vamos a pasar los argumentos: nuestro estado inicial, nuestra función de paro y la cota. Pero aquí, como cota, vamos a pasar nuestro contador. Después vamos a incrementar el contador. Ya terminamos nuestro bloque asociado a esta repetición "while".
básicamente el algoritmo de profundidad iterada lo que hace es una serie de invocaciones al algoritmo DLS, en la cual se va incrementando, en cada invocación, la profundidad de corte. De esta manera, mientras estemos abajo de la profundidad de la solución, DLS nos va a regresar una solución inexistente y el algoritmo va a continuar iterando. Aquí, mientras la solución sea igual a "none", o sea que no exista, va a continuar iterando. En el momento en que le demos la profundidad de la solución, o sea, que esta profundidad "i" sea igual a nuestro parámetro "c", entonces, DLS la va a encontrar y nos la va a dar. En ese momento, la solución va a ser diferente de "none" y la regresamos.
Depth first branch and bound.
Esta es una mejora sobre el algoritmo de profundidad iterada: el algoritmo DFBB tiene tres argumentos. El primero es el estado inicial, el segundo es la función de paro, y el tercero es la cota de profundidad a la cual la vamos a denominar "c". Esta cota va a servir para controlar hasta dónde se van a expandir los nodos. Ahora, vamos a inicializar primero nuestra solución como no existente. Después, vamos a verificar la condición trivial, esto es, si la función de paro se satisface para el estado inicial. Si esto es cierto, entonces, regresamos la ruta, que aquí va a ser trivial.
Para ello, asumimos que existe una función que nos encuentra la ruta. Si la condición trivial no se cumple, lo siguiente es inicializar la agenda con el estado inicial. Entonces, vamos a agregar el estado inicial a la agenda. Ya que terminamos de inicializar, lo siguiente es entrar en un ciclo de iteración. El ciclo de iteración lo voy a escribir de este lado. Aquí ponemos que continúa en "alfa". En el ciclo "while" vamos a poner la condición de que la agenda no esté vacía.
relatedInteligencia Artificial