BUSQUEDAS

Búsqueda en anchura

Como su nombre indica, el recorrido realizado se lleva a cabo visitando todos los nodos de un nivel, de izquierda a derecha, pasando posteriormente al nivel siguiente, hasta que se encuentre el nodo objetivo, momento en el que se detiene el algoritmo. Lo vemos en el dibujo con el mismo ejemplo de antes, numerando los nodos con el orden que les corresponde según el recorrido en anchura.

En efecto, los nodos que con este algoritmo se visitan hasta encontrar el objetivo (8) son: 1-> 2-> 3-> 4-> 5-> 6-> 7-> 8

Su complejidad tanto espacial como temporal es exponencial, y está en O (n^p), siendo n el número medio de sucesores, y p el nivel donde se alcanza la solución; por ello, esta estrategia es sólo aplicable a problemas no demasiado amplios.

Este procedimiento es completo, ya que encontrará siempre una solución si es que la hay, pero en general no es óptimo. Para implementarlo se ha hecho uso de una cola FIFO.

halla_objetivo_anchura (A: espacio_de_busquedas)

  { /* dev objetivo*/

     Cola lista_nodos;

     Boolean acabar = false;

     lista_nodos.encolar (A.nodo_raiz);

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

     {

        nodo_actual = lista_nodos.primero(); 

        lista_nodos.quitaPrimero();

        if (esObjetivo (nodo_actual) ) then

           {

                acabar = true;

           }

        else

           {

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

                   lista_nodos.encolarMuchos (nodos_expandidos_de_nodo_actual);

           }

     }

     return nodo_actual;

  }