Búsqueda en profundidad

Definición

Estrategia no informada que expande primero el nodo más profundo de la frontera. Se implementa con una pila LIFO o mediante recursión.

Regla

$f(n)=-\mathrm{profundidad}(n),$

entendida como una prioridad que favorece mayor profundidad. No compara costos ni cercanía a la meta.

Propiedades

• Tiempo: $O(b^m)$.
• Espacio: $O(bm)$.
• No es óptima.
• No es completa en búsqueda en árbol con ciclos o profundidad infinita.
• En un grafo finito, con registro correcto de estados alcanzados, sí termina y es completa.

Intuición

Explora una rama hasta agotarla y después retrocede. Su memoria es pequeña porque conserva principalmente el camino actual y los hermanos pendientes, pero puede invertir todo el tiempo en una rama sin solución.

Relaciones

• Es una búsqueda no informada.
• Su versión con límites crecientes es profundidad iterativa.
• Se evalúa con los criterios de búsqueda.