búsqueda en profundidad iterativa
Iterative Deepening Search (IDS)
1. Introducción
El algoritmo de búsqueda de profundización iterativa es una técnica utilizada en
inteligencia artificial para buscar soluciones en un espacio de búsqueda. A diferencia de
otros algoritmos de búsqueda, como BFS (búsqueda en amplitud) y DFS (búsqueda en
profundidad), IDS ofrece una combinación única de eficiencia en espacio y garantía de
completitud. En este artículo, exploraremos cómo funciona este algoritmo y las ventajas
que ofrece en comparación con otros métodos de búsqueda.
Antes de adentrarnos en el IDS, es importante comprender las diferencias entre BFS y
DFS. BFS es conocido por su espacio complejidad exponencial, lo que significa que
requiere una cantidad significativa de memoria, especialmente para espacios de
búsqueda grandes. Por otro lado, DFS utiliza menos memoria que BFS, ya que solo
guarda una ruta en lugar de todas las rutas posibles. Sin embargo, DFS no garantiza la
completitud, lo que significa que puede quedarse atascado en ciclos y no encontrar una
solución.
Una pregunta que puede surgir es si es posible diseñar un algoritmo de búsqueda que
aproveche los beneficios de BFS y DFS al mismo tiempo. La respuesta es sí, y ese
algoritmo es IDS. El IDS combina de manera inteligente los aspectos positivos de
ambos algoritmos, ofreciendo una solución que es eficiente en espacio y garantiza la
completitud.
2. Estructuras de datos involucradas:
Pila (Stack)
Descripción: Una pila es una estructura de datos que sigue el principio LIFO (Last In,
First Out), donde el último elemento en entrar es el primero en salir.
Importancia: En IDS, la pila se utiliza para realizar la búsqueda en profundidad.
Almacena los nodos que se están explorando actualmente y permite retroceder cuando
se alcanza un nodo sin hijos o una solución. Esto facilita el retroceso y avance en el
árbol de búsqueda.
Árbol de Búsqueda
Descripción: Un árbol de búsqueda es una estructura jerárquica donde cada nodo
representa un estado posible del problema y las aristas representan las acciones que
llevan de un estado a otro.
Importancia: Representa el espacio de búsqueda de manera clara y organizada,
permitiendo visualizar todas las posibles rutas y soluciones. Es fundamental para
estructurar el problema y guiar la búsqueda.
Lista de Nodos Visitados
Descripción: Una lista de nodos visitados es una estructura que almacena los nodos que
ya han sido explorados.
Importancia: Aunque no siempre es necesaria, ayuda a prevenir la exploración repetida
de los mismos nodos, mejorando la eficiencia al evitar ciclos y redundancias.
Cola (Queue)
Descripción: Una cola es una estructura de datos que sigue el principio FIFO (First In,
First Out), donde el primer elemento en entrar es el primero en salir.
Importancia: En algunas variantes del algoritmo, una cola puede ser utilizada para
gestionar los nodos a explorar en cada nivel de profundidad, asegurando que se
procesen en el orden correcto.
Grafos
Descripción: Un grafo es una estructura compuesta por nodos (o vértices) y aristas (o
enlaces) que conectan pares de nodos.
Importancia: En problemas donde los estados y transiciones no forman un árbol, sino
una red más compleja, los grafos permiten representar y explorar todas las posibles
conexiones y rutas.
3. Análisis de la eficiencia de IDS
El algoritmo de búsqueda de profundización iterativa comienza con un límite de
profundidad de 0 y lo va incrementando hasta que encuentra el nodo objetivo. Para cada
límite de profundidad, IDS realiza una búsqueda en profundidad (DFS) hasta el límite
establecido. Esto implica que, si un nodo alcanza el límite de profundidad, IDS no
generará y agregará sus sucesores a la frontera. En esencia, IDS retrocede cuando
alcanza el límite de profundidad y, cada vez que incrementamos este límite, IDS
comienza nuevamente la búsqueda en profundidad desde el principio.
Para comprender mejor cómo funciona IDS, consideremos un grafo de búsqueda y
tracemos su ejecución utilizando el algoritmo. A medida que avanzamos en la
explicación, agregaré nodos al grafo y describiré los pasos de ejecución de IDS de
manera detallada.
Imagina que tenemos un grafo simple con nodos numerados del 1 al 7, y queremos
encontrar el nodo 7 comenzando desde el nodo 1. El grafo se ve así:
2 3
4 5 6 7
Pasos del algoritmo IDS:
Profundidad 0:
Explora el nodo 1.
No encuentra el nodo 7.
Profundidad 1:
Explora el nodo 1.
Explora los nodos 2 y 3.
No encuentra el nodo 7.
Profundidad 2:
Explora el nodo 1.
Explora los nodos 2 y 3.
Explora los nodos 4, 5, 6 y 7.
Encuentra el nodo 7.
Profundidad 0: 1
Profundidad 1: 1 -> 2, 1 -> 3
Profundidad 2: 1 -> 2 -> 4, 1 -> 2 -> 5, 1 -> 3 -> 6, 1 -> 3 -> 7
En cada iteración, el algoritmo incrementa la profundidad límite y explora todos los
nodos hasta esa profundidad antes de incrementar nuevamente. Esto asegura que se
exploren todas las posibles rutas de manera eficiente en términos de memoria.
Complejidad Temporal y Espacial en IDS
El algoritmo de búsqueda en profundidad iterativa (IDS) tiene una complejidad que
combina aspectos de la búsqueda en profundidad (DFS) y la búsqueda en amplitud
(BFS). Aquí te dejo un resumen de su complejidad:
Complejidad Temporal
La complejidad temporal de IDS es similar a la de BFS en el peor de los casos, pero con
un factor adicional debido a la repetición de búsquedas en profundidad hasta alcanzar la
profundidad deseada. La complejidad temporal es:
O(b^d), donde:
b es el factor de ramificación (el número promedio de hijos por nodo).
d es la profundidad del nodo objetivo.
complejidad temporal es 𝑂(1).
Mejor Caso: En el mejor caso, si la solución se encuentra en el primer nivel, la
Complejidad Espacial
La complejidad espacial de IDS es similar a la de DFS, ya que solo necesita almacenar
un camino desde la raíz hasta el nodo actual y los nodos hermanos en la frontera. La
complejidad espacial es:
O (b * d), donde:
b es el factor de ramificación.
d es la profundidad del nodo objetivo.
Por ejemplo:
Si estás buscando una solución en un árbol con un factor de ramificación de 3 y una
profundidad de 4, la complejidad temporal sería O(3^4)=O(81)O(3^4) = O(81) en el
peor caso, y la complejidad espacial sería O(3*4)=O(12)
Ventajas de IDS
Completo: Siempre encuentra una solución si existe.
Óptimo: Encuentra la solución más corta si todos los pasos tienen el mismo costo.
Eficiente en memoria: Utiliza menos memoria que BFS.
Desventajas de IDS
Repetición de trabajo: Realiza múltiples búsquedas en profundidad, lo que puede ser
ineficiente en términos de tiempo.
En resumen, IDS es una técnica poderosa que combina las ventajas de DFS y BFS,
siendo completa y óptima, pero puede ser costosa en términos de tiempo debido a la
repetición de búsquedas.
Completitud y optimalidad de IDS
En términos de completitud, IDS garantiza encontrar la solución si existe una. A
diferencia de DFS, IDS no seguirá caminos infinitos, ya que solo realiza una búsqueda
en profundidad hasta un límite establecido. Por lo tanto, IDS es completo y garantiza
encontrar la solución si existe.
En cuanto a la optimalidad, IDS, al igual que otros algoritmos de búsqueda no
informados, no tiene en cuenta los costos de las aristas. Esto significa que IDS no
garantiza la calidad de la solución encontrada. Sin embargo, debido a que IDS aumenta
el límite de profundidad de manera Incremental, puede lograr el mismo nivel de
optimalidad que BFS. En otras palabras, IDS está garantizado para encontrar el nodo
objetivo más cercano en términos de profundidad si todas las aristas tienen el mismo
costo.
Algoritmo de Búsqueda de Profundización Iterativa nativa (IDS)
En su forma iterativa
IDS(raíz, objetivo)
{
profundidad = 0
repetir
{
resultado = IDS(raíz, objetivo, profundidad)
Si (resultado es una solución)
devolver resultado
profundidad = profundidad + 1
}
}
Una búsqueda en profundidad limitada se puede implementar de forma recursiva como
sigue. Nótese que solo tiene que comprobar los nodos objetivos cuando profundidad ==
0, porque cuando profundidad > 0, BPL expande nodos que han sido visitados en
iteraciones previas de IDS.
BPL(nodo, objetivo, profundidad)
{
Si (profundidad == 0 y nodo == objetivo)
devolver nodo
sino si (profundidad > 0)
para cada hijo en expandir(nodo)
resultado = BPL(hijo, objetivo, profundidad-1)
si resultado distinto de null
devolver resultado
sino
devolver null
}
El algoritmo de búsqueda de profundización iterativa (IDS) es ampliamente
utilizado en videojuegos y problemas complejos debido a su eficiencia en
memoria y su capacidad de garantizar la completitud en la exploración de
grandes espacios de búsqueda. Aquí exploramos cómo se aplica este
algoritmo en distintos videojuegos y problemas estratégicos.
4.1. Ajedrez: Una Aplicación Clásica
El ajedrez es uno de los ejemplos más estudiados para la aplicación de IDS.
Los motores de ajedrez modernos, como Stockfish, lo emplean para analizar
posibles movimientos y estrategias, especialmente en combinación con otros
algoritmos como Minimax y poda Alpha-Beta.
Ventajas en Ajedrez:
Permite una respuesta rápida al limitar inicialmente la profundidad de búsqueda
y aumentarla progresivamente.
Reduce el uso de memoria al explorar una rama del árbol de decisiones a la
vez.
Garantiza la mejor solución posible dentro del límite de profundidad
establecido.
4.2. Go: El Desafío de un Espacio de Búsqueda Inmenso
El Go, conocido por su inmensa complejidad, utiliza IDS como base en algunos
motores tradicionales, especialmente antes del auge de las redes neuronales
profundas. Este enfoque permite explorar estrategias iniciales y posibles
configuraciones del tablero con recursos computacionales limitados.
4.3. Juegos de Mesa y Cartas: Backgammon y Juegos Similares
En juegos como el Backgammon, IDS permite explorar estrategias
considerando la aleatoriedad introducida por dados o cartas. Se emplea para
evaluar diferentes combinaciones de movimientos y predecir las respuestas del
oponente dentro de escenarios específicos.
4.4. Puzles y Juegos de Resolución
IDS es ideal para resolver puzles clásicos y videojuegos que plantean desafíos
estructurados como:
Cubo de Rubik: Cada nodo del árbol de búsqueda representa una
configuración del cubo, y IDS explora las posibles soluciones aumentando
progresivamente el límite de movimientos.
Rompecabezas de las 8 piezas: Este juego implica encontrar el orden
correcto de las piezas deslizándolas en un tablero. IDS permite buscar las
soluciones más eficientes evitando ciclos.
4.5. Videojuegos Modernos de Exploración y Estrategia
IDS también tiene aplicaciones prácticas en videojuegos modernos que
requieren toma de decisiones estratégicas o exploración sistemática. Algunos
ejemplos incluyen:
Civilization:
En esta serie de juegos de estrategia, IDS puede usarse para evaluar
decisiones a largo plazo, como la construcción de ciudades, la selección de
tecnologías o la planificación militar.
Permite encontrar rutas óptimas en mapas complejos y evaluar el impacto de
las decisiones en iteraciones controladas.
StarCraft:
En este videojuego de estrategia en tiempo real, IDS puede ser empleado para
planificar movimientos estratégicos, como atacar o defender en distintos puntos
del mapa.
La combinación de IDS con heurísticas específicas ayuda a gestionar unidades
y recursos.
The Legend of Zelda (puzles y exploración):
En videojuegos de la saga Zelda, IDS es útil para resolver problemas de
exploración en mazmorras, donde cada estado del árbol representa la posición
actual del jugador y los pasos para alcanzar el objetivo.
Pac-Man:
IDS puede emplearse para planificar las rutas de los fantasmas en tiempo real,
buscando patrones óptimos para interceptar al jugador.
4.6. Juegos Basados en Movimiento y Navegación
IDS es particularmente útil en juegos que implican navegación en laberintos o
entornos desconocidos:
Minecraft:
En el modo de supervivencia, los bots o NPCs pueden usar IDS para explorar
áreas desconocidas y buscar recursos, optimizando rutas en mapas generados
proceduralmente.
Portal:
Los algoritmos basados en IDS pueden ser utilizados para resolver los
rompecabezas de portales en busca de soluciones óptimas en niveles
complejos.
4.7. Videojuegos de Simulación y Competencia
En simulaciones como las carreras o juegos deportivos, IDS puede ayudar a
evaluar estrategias para alcanzar un objetivo específico:
FIFA:
IDS puede aplicarse para planificar secuencias de pases y tiros basados en el
posicionamiento dinámico de los jugadores en el campo.
Gran Turismo:
IDS permite analizar trayectorias ideales en circuitos de carreras, evaluando
velocidades y puntos de frenado en iteraciones progresivas.