BÚSQUEDA PRIMERO EN PROFUNDIDAD

Fecha de clase: 03/junio/2014

BÚSQUEDA PRIMERO EN PROFUNDIDAD O BÚSQUEDA CON VUELTA ATRÁS

Esta estrategia intenta seguir un camino hasta la mayor profundidad posible, retrocediendo cuando acaba el camino y retomando la última posibilidad de elección disponible.

El principal problema de este algoritmo es que no acaba si existe la posibilidad de que hayan caminos infinitos. Una variante de este algoritmo que evita este problema es el algoritmo de profundidad limitada (Búsqueda en profundidad prioritaria), éste impone un límite máximo de profundidad que determina la longitud máxima de los caminos recorridos. Esta limitación garantiza que el algoritmo acaba, pero no garantiza encontrar la solución, ya que ésta puede estar a mayor profundidad que el límite impuesto. (UNIVERSITAT POLITÉCNICA DE CATALUNYA, 2013)

Este método sólo genera un sucesor del nodo en cada paso y cada nodo llevará  una marca que indique qué operadores se pueden utilizar especificando el orden de aplicación, hasta llegar a una profundidad límite. Lo que se busca con esta profundidad límite es no realizar una búsqueda innecesaria; es decir desecha los las partes del grafo donde el nodo objetivo este muy lejano al nodo inicial.

Los nodos están ordenados según su profundidad, en orden creciente: los más profundos al principio, los menos profundos al final, conviertiendose en una PILA: los datos que primero entran son los últimos en salir. (Rubio et al. 1998)

Al igual que sucedía en la búsqueda en anchura, los nodos de igual profundidad se ordenan arbitrariamente, según el orden de las reglas u operadores.

Entonces este método también se lo conoce como vuelta atrás (cronológica) porque se establece la profundidad y al llegar al nodo límite sin alcanzar el nodo objetivo habría que regresar al nodo inmediatamente superior (el nodo límite ya revisado se lo debe desechar porque es obvio que no se pueden crear más sucesiones de él) y volver a realizar una búsqueda en este nodo y como este vendría a ser el nodo límite-1 podemos desprender otro nodo (último) y si en ésta parte del grafo tampoco se encuentra se realiza el mismo procedimiento anteriormente mencionado.

Figura 2. Generación de los primeros nodos en la búsqueda  primero en profundidad Autor: Nils, J. (2001)

La Búsqueda en profundidad iterativa lo que se hace es repetir sucesivamente el algoritmo de profundidad limitada, aumentando a cada iteración la profundidad máxima a la que le permitimos llegar. Este algoritmo obtendría el mismo efecto que el recorrido en anchura en cada iteración, ya que a cada paso recorremos un nivel más del espacio de búsqueda. (UNIVERSITAT POLITÉCNICA DE CATALUNYA, 2013)

La ventaja de este proceso (Búsqueda en profundidad) es que el coste en memoria crece de forma lineal. La contraparte de esta estrategia es que el ir del límite hacia el inicio no asegura que la solución encontrada sea la óptima (más cercana o de menor profundidad) o el hecho de revisar varias partes del grafo que se encuentren lejanas, pudiendo estar cerca la solución.

BIBLIOGRAFÍA

Nils J. Nilsson. 2001. INTELIGENCIA ARTIFICIAL. Una nueva síntesis.  ISBN: 1-55860-467-7.  1era ed. Copyright MCMXCVIII by Morgan Kaufmann Publishers, Inc.

Bibliografía Complementaria

UNIVERSITAT POLITÉCNICA DE CATALUNYA, 2013. Departament de Llenguatges i Sistemes Informátics. APUNTS D’INTEL.LIGE`NCIA ARTIFICIAL. Formato (PDF). Disponible en: http://www.lsi.upc.edu/~bejar/ia/material/teoria/ApuntesIA.pdf

Rubio, J; Muro, P. y Bañares, J. 1998. Inteligencia Artificial e Ingeniería del Conocimiento I. BÚSQUEDA. Departamento de Informática e Ingeniería de Sistemas Universidad de Zaragoza. Curso 96-97. Formato (PDF). Disponible en: http://www.lsi.upc.edu/~bejar/iia/iabusq.pdf