Este tipo de algoritmos recorre el espacio de estados de una forma concreta hasta dar con el objetivo.
Supongamos el árbol del dibujo representando un espacio de estados cualquiera. Vemos que, teniendo este árbol delante con sus nodos numerados, tenemos distintas formas de recorrerlo. ¿Cómo lo hacemos en profundidad? Siendo el 1 el nodo inicial y 7 el nodo objetivo que se debe alcanzar, hacemos lo siguiente: buscaremos en todas las ramas que cuelgan, de izquierda a derecha, y exploramos cada rama hasta llegar a una hoja. Para cada hijo buscamos a su vez en profundidad, parando cuando se encuentre el objetivo. En este ejemplo, la secuencia a seguir está indicada por el número de los nodos: 1-> 2-> 3-> 4-> 5-> 6-> 7.
Si el camino tiene longitud k y factor de ramificación r, la complejidad espacial del algoritmo está en O (kr). Su complejidad temporal depende tanto del factor de ramificación como de la profundidad de la solución. Siendo n el número medio de hijos expandidos, y si la solución se alcanza en el nivel p, la complejidad temporal está en O (n^p); es, por tanto, un coste exponencial.
Este algoritmo de búsqueda, además, no es completo, ya que si existe solución y se mete por una rama infinita puede que no termine nunca. Tampoco es óptimo, ya que puede encontrar la solución pero haciendo un recorrido mayor del necesario en general. Se ha usado una estructura pila LIFO para implementarlo.
No hay comentarios:
Publicar un comentario