BUSQUEDAS DE PROFUNDIDAD

Supongamos que nuestro robot no tiene ninguna capacidad especial para poder moverse por la habitación de una manera eficiente (desconoce cualquier información útil para poder llegar al libro de la forma más corta): entonces deberá seguir un algoritmo de búsqueda no informada (“un método ciego”) para llegar hasta él. En general, este tipo de algoritmos recorre el espacio de estados de una forma concreta hasta dar con el objetivo (en este caso, el libro). Nuestro primer método se denomina búsqueda en profundidad.

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.

halla_objetivo_profundidad (A: espacio_de_busquedas)

  { /* dev objetivo*/

     Pila lista_nodos;

     Boolean acabar = false;

     lista_nodos.apilar (A.nodo_raiz);

     while ((!lista_nodos.esVacia()) AND (!acabar)) do

     {

        nodo_actual = lista_nodos.cima(); 

        lista_nodos.desapila();

        if (esObjetivo (nodo_actual) ) then

           {

                acabar = true;

           }

        else

           {

                  nodo_actual.expandir(); //se añaden los hijos del nodo actual

                   lista_nodos.apilarMuchos (nodos_expandidos_de_nodo_actual);

           }

     }

     return nodo_actual;

 }