BUSQUEDA DE PROFUNDIDAD LIMITADA

Fecha de clase: 16 de Octubre

INTRODUCCIÓN

En esta clase se aprendió sobre las diferentes búsquedas no informadas, como todas las clases se empezó con el narrador y el expositor sobre la búsqueda de profundidad limitada, búsqueda con profundidad iterativa, búsqueda bidireccional cabe recalcar que estas son herramientas para la búsqueda de solución de un problema.

MARCO TEÓRICO

BUSQUEDA DE PROFUNDIDAD LIMITADA

Se puede aliviar el problema de árboles ilimitados aplicando la búsqueda primero en profundidad con un límite de profundidad t predeterminado. Es decir, los nodos a profundidad i se tratan como si no tuvieran ningún sucesor. A esta aproximación se le llama búsqueda de profundidad imitada El límite de profundidad resuelve el problema del camino infinito. Lamentablemente, también introduce una fuente adicional de incompletitud si escogemos € < d, es decir, el objetivo está fuera del límite de profundidad.

La búsqueda de profundidad limitada también será no óptima si escogemos i > d. Su complejidad en tiempo es 0(kf) y su complejidad en espacio es 0(bí). La búsqueda primero en profundidad puede verse como un caso especial de búsqueda de profundidad limitada con t = infinito. (Rentería, R)

BUSQUEDA DE PROFUNDIDAD ITERATIVA

Intenta combinar el comportamiento espacial de la búsqueda en  profundidad (DFS) con la optimalidad de la búsqueda en anchura  (BFS), por esto es el más ventajoso de los anteriores. El algoritmo consiste en realizar búsquedas en profundidad  sucesivas con un nivel de profundidad máximo acotado y creciente  en cada iteración. Así se consigue el comportamiento de BFS pero sin su coste  espacial, ya que la exploración es en profundidad, y además los  nodos se regeneran a cada iteración. Además esto permite evitar los casos en que DFS no acaba (existen  ramas infinitas).

En la primera iteración la profundidad máxima será 1 y este valor irá aumentando en sucesivas iteraciones hasta llegar a la solución. Para garantizar que el algoritmo acaba si no hay solución, se puede definir una cota máxima de profundidad en la exploración. (Russell, S y Norvig, P)

BUSQUEDA BIDIRECCIONAL

La idea de la búsqueda bidireccional es ejecutar dos búsquedas simultáneas: una hacia delante desde el estado inicial y la otra hacia atrás desde el objetivo, parando cuando las dos búsquedas se encuentren en el centro. La motivación es que b^d/2 + b^d/2 es mucho menor que b^d, o en la figura, el área de los dos círculos pequeños es menor que el área de un círculo grande centrado en el inicio y que alcance al objetivo. La búsqueda bidireccional se implementa teniendo una o dos búsquedas que comprueban antes de ser expandido si cada nodo está en la frontera del otro árbol de bús queda; si esto ocurre, se ha encontrado una solución.

CONCLUSIÓN

Este es un método que consiste buscar mejores soluciones óptimas y que puedan solucionar los problemas planteados es necesario mencionar que existen diferentes formas de interpretar una búsqueda, es decir existe dos que son una búsqueda informativa y la búsqueda a ciegas.

BIBLIOGRAFÍA

Russell, S y Norvig, P. 2004.  INTELIGENCIA ARTIFICIAL. UN ENFOQUE MODERNO. Segunda edición.  PEARSON EDUCATION, S.A. Impreso en España.

Rentería, R. 2010. Búsqueda no Informada. Formato PDF. (En línea). Disponible en clasev.net/v2/mod/resource/view.php?id=11783