ALGORITMO DE BÚSQUEDA: BREADTH FIRST SEARCH

Posted: December 6, 2010 in Algoritmos

[Saludos, les escribe Jhosimar Arias autor de los tutoriales aqui mostrados y parte de algunos posts. Escribo este post para hacerles llegar mi blog propio:

http://jariasf.wordpress.com/

Traslade mis 2 tutoriales de DFS y BFS, asi mismo agregue algunas cosas a ambos como mas imagenes en el caso de DFS y un punto mas en el BFS. Posteare mas tutoriales en mi propio blog asi como soluciones de problemas de jueces que parezcan interesantes.]

Hola a todos como bien sabemos los concursos de programación no solo se basan en tener una idea para resolver un problema (ad hoc) o usar la fuerza bruta, varios problemas requieren mas que ese tipo de soluciones es necesario tener conocimiento de diversos algoritmos para poder resolver este tipo de problemas, en esta oportunidad queremos mostrarles algoritmos de grafos que son bastante usados, vamos a empezar por los algoritmos de búsqueda ya que son bastante comunes y faciles de aprender estos algoritmos son DFS(Deaph First Search – Busqueda por profundidad) y BFS(Breadth First Search – Busqueda por Anchura)

En esta oportunidad mostraremos el algoritmo de búsqueda por anchura en un grafo (BFS) , explicaremos el algoritmo y propondremos algunos problemas que se solucionan con este algoritmo para que puedan resolverlos.

Descripción

Este algoritmo de grafos es muy útil en diversos problemas de programación. Por ejemplo halla la ruta más corta cuando el peso entre todos los nodos es 1, cuando se requiere llegar con un movimiento de caballo de un punto a otro con el menor numero de pasos, cuando se desea tranformar algo un numero o cadena en otro realizando ciertas operaciones como suma producto, pero teniendo en cuenta que no sea muy grande el proceso de conversion,  o para salir de un laberinto con el menor numero de pasos , etc. Podrán aprender a identificarlos con la práctica.

Como trabaja

BFS va formando un árbol a medida que va recorriendo un grafo,  veamos el ejemplo de la figura:

Si observan bien todo parte de un nodo inicial que será la raiz del árbol que se forma, luego ve los adyacentes a ese nodo y los agrega en un cola, como la prioridad de una cola es FIFO (primero en entrar es el primero en salir), los siguientes nodos a evaluar serán los adyacentes previamente insertados. una cosa bastante importante es el hecho de que no se pueden visitar 2 veces el mismo nodo o Estado. ya que sino podriamos terminar en un ciclo interminable o simplemente no hallar el punto deseado en el menor número de pasos.

Dos ejemplos mas detallados lo puede ver desde aqui ->EJEMPLO1 BFS ,   EJEMPLO2 BFS

Algoritmo en pseudocódigo

1  método BFS(Grafo,origen):
2      creamos una cola Q
3      agregamos origen a la cola Q
4      marcamos origen como visitado
5      mientras Q no este vacío:
6          sacamos un elemento de la cola Q llamado v
7          para cada vertice w adyacente a v en el Grafo: 
8              si w no ah sido visitado:
9                 marcamos como visitado w
10                 insertamos w dentro de la cola Q

Ejemplo Aplicativo:

Tenemos una matriz de caracteres que representa un laberinto 2D un ‘#’ implica un muro, un ‘.’ implica un espacio libre, un ‘I’ indica la entrada del laberinto y una ‘S’ indica una salida.

¿Cuánto mide la ruta más corta para escapar?

Solución:

El problema nos da un Estado inicial y final, en este caso “I” y “S”, nos pide el menor numero de pasos para ir de “I” a “S” tomando en consideración que solo podremos avanzar por los “.”

Dicha la descripción anteriro,  el problema puede ser resulto por BFS al tener un estado inicial y final eh ir avanzando por algun adyacente que no sea “#” . Los posibles adyacentes para movernos es hacia arriba, abajo, izquierda y derecha, suponiendo que estamos en la posición (x,y) tendriamos:

Asi por ejemplo si estoy en la posición siguiente (circulo) y suponiendo que sea la coordenada 3,4 :

Los posibles Estados adyacentes serian: izquierda (3,2 -> “.”), derecha (3,5 -> “.”), arriba (2,4 -> “#”) y abajo (4,4 -> “#”) por lo tanto para ese caso solo podriamos avanzar por la derecha o izquierda.

La solución la explicaremos paso a paso en el lenguaje C++ , para otros lenguajes como Java es bastante similar.

Primeramente declaramos nuestro laberinto como una matriz, tambien declaramos un arreglo de Visitado que nos indicará si se visito o no un estado determinado:

#define MAX 100 //máximo número de filas y columnas del laberinto
char ady[MAX][MAX];   //laberinto
bool visitado[MAX][MAX]; //arreglo de estados visitados

Para la función BFS, la entrada que se recibe es el punto inicial de donde deseamos partir y el punto de llegada,  en este ejemplo el punto de llegada esta representado por “S” por lo que no es necesario pasarlo como parametro. El valor inicial cuando trabajamos con dos dimensiones es necesario la fila y columna inicial, ademas tenemos que pasar la altura y el ancho del laberinto para controlar los limites de recorrido estos podemos declararlos globales si se desea:

int BFS(int x , int y, int h, int w)   //coordenadas de inicial "I" y dimensiones de laberinto

Cada vez que trabajamos con BFS trabajamos con estados, desde un estado inicial podemos llegar al estado final por medio de varios estados, por ello una forma de manejar los diferentes estados y los valores que se tiene hasta ese estado podemos realizar una estructura “Estado” que contendrá la posición del estado determinado asi como otros atributos, uno necesario es la distancia en dicho estado:

struct Estado{
  int x;  // Fila del estado
  int y;  // Columna del estado
  int d;  // Distancia del estado
  Estado(int x1 , int y1 , int d1) : x(x1), y(y1), d(d1){}  // Constructor
};

Respecto a lo anterior otra forma para hallar las distancias sería ir almacenando en un arreglo de distancias. Declaramos nuestro estado inicial:

Estado inicial(x,y,0) ; //Estado inicial, distancia = 0

Ahora para realizar un BFS es necesario la estructura de datos Cola, la cual pondemos implementar por medio de arreglos o simplemente usar la estructura ya implementada de las librerias de C++ (queue) o Java(Queue):

queue<Estado> Q;   //Cola de todos los posibles Estados por los que se pase para llegar al destino
Q.push(inicial); //Insertamos el estado inicial en la Cola.

Nuestro arreglo de visitados es necesario inicializarlo como no visitado inicialmente:

memset(visitado, false, sizeof(visitado)); //marcamos como no visitado

Ahora a partir del inicial comprobamos si se llego al destino, en caso sea verdadero retornamos la distancia recorrida hasta ese momento, de otro modo empezamos a evaluar los adyacentes y agregarlos a la cola. Para evaluar los adyacentes se explico anteriormente que son dados en 4 direcciones ello se puede expresar de la siguiente manera:

int dx[4] = {0, 0, 1, -1 };  //incremento en coordenada x
int dy[4] = {1, -1, 0, 0 };  //incremento en coordanada y

Estos valores seran usados para aumentar al estado actual y ver su adyacente, esto se explico anteriormente en la grafica ejemplo de recorrido.

Haremos todo este proceso descrito anteriormente mientras la cola no este vacia:

while( !Q.empty() ){                  //Mientras cola no este vacia
   Estado actual = Q.front();         //Obtengo de la cola el estado actual, en un comienzo será el inicial
   Q.pop();                           //Saco el elemento de la cola
   if( ady[actual.x][actual.y]== 'S'){//Si se llego al destino (punto final)
     return actual.d;                 //Retornamos distancia recorrida hasta ese momento
   }
   visitado[actual.x][actual.y]=true; //Marco como visitado dicho estado para no volver a recorrerlo
   for( int i = 0; i < 4; i++){       //Recorremos hasta 4 porque tenemos 4 posibles adyacentes
      int nx = dx[i] + actual.x;      //nx y ny tendran la coordenada adyacente
      int ny = dy[i] + actual.y;      //ejemplo en i=0 y actual (3,4) -> 3+dx[0]=3+0=3, 4+dy[0]=4+1=5, nueva coordenada (3,5)
      //aqui comprobamos que la coordenada adyacente no sobrepase las dimensiones del laberinto
      //ademas comprobamos que no sea pared "#" y no este visitado
      if(nx>=0 && nx<h && ny>=0 && ny<w && ady[nx][ny]!='#' && !visitado[nx][ny]){
         Estado adyacente(nx, ny, actual.d+1);  //Creamos estado adyacente aumento en 1 la distancia recorrida
         Q.push(adyacente);                     //Agregamos adyacente a la cola
      }
   }

}

Finalmente si no se pudo llegar al destino retornamos un valor que el problema comunmente nos da en este caso podemos retornar -1.

A continuación dejamos una lista de problemas que pueden ser resueltos con este algoritmo:

Juez UVA

336 A Node Too Far

383 Shipping Routes

429 – Word Transformation

439 – Knight Moves

532 – Dungeon Master

627 – The Net

762 – We Ship Cheap

10653 – Bombs! NO they are Mines!!

11730 – Number Transformation

Para mas problemos en el UVA pueden encontrarlos en el UvaToolkit escribiendo en el buscador BFS.

Juez TJU

1056 – Labyrinth

1098 – The Separator Grid

2470 – Robot in Maze

2560 – The Explorer

2648 – Print Path

Juez HDU

1242 – Rescue

1195 – Open the Lock

1072 – Nightmare

3713 – Double Maze

1312 – Red and Black

1240 – Asteroids

Topcoder

SRM 397 DIV 2, Problema de 500 puntos

SRM 486 DIV 2, Problema de 500 puntos

SRM 302 DIV 2, Problema de 900 puntos

ICPC LIVE

2040 – Multiple

2616 – I hate SPAM, but some people love it

3687 – Footbal Foundation (FOFO)

4461 – Easy Does It!

Códigos:

Implementación del algoritmo en Java: Algoritmo BFS

Implementación del algoritmo en C++: Algoritmo BFS

Ejemplo BFS en Java: Saliendo del Laberinto

Ejemplo BFS en C++: Saliendo del Laberinto

Por Jhosimar George Arias Figueroa

Comments
  1. Jose Herrera says:

    Muy interesante, gracias. yo recien comienzo con los programming contest, y es muy util encontrar estas explicaciones.
    Saludos

    • Digberth says:

      Si esta muy buena la explicación del algoritmo xD, continúen haciendo de más algoritmos (especialmente los de DP). Estaré atento😛.

      Saludos.

  2. raynerhmc says:

    Si ps , por ahora estamos muy ocupados con los cursos de la carrera, pero en cuando acabe esto, se postearán mas tutoriales. Keep solving!!

  3. Dennis says:

    hola, excelente post, espero que continuen para un DFS y un dijsktra, con la misma estructura con la que presentaron esta, muchas gracias ¡¡¡

  4. Carlos says:

    Realmente pasado el post. Necesito hacer una exposición sobre recorridos en grafos y andaba buscando bibliografía clara para poder entender y explicarlo mejor y aquí la encontre a diferencia de los libros de texto (de que sirven las demostraciones matemáticas sirven pero necesitaba un poco de ejemplos).

    Buenísima página.

  5. jackajack says:

    Tremenda explicacion…. es la 2da tarea que hago gracias a tus post… sigue asi😄

  6. expiation says:

    Now that I’ve just spent six hours on your website reading your posts, I’m absolutely hooked on your blog.

    I bookmarked it as well so that I can keep up with it frequently.
    Be sure to visit my blog as well and tell me what you
    think.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s