Diferencias

Muestra las diferencias entre dos versiones de la página.

--- algoritmos-oia:grafos:bfs [2018/01/05 21:04]
santo
+++ algoritmos-oia:grafos:bfs [2018/01/05 22:58] (actual)
santo [Cálculo de distancias]
@@ Línea 1: / Línea 1: @@
 ====== BFS ======
-La página de BFS está pendiente de mejorar.
+BFS es una técnica para **recorrer** un [[algoritmos-oia:grafos|grafo]], a partir de **un nodo origen**. Proviene de la sigla en inglés "Breadth First Search", que podríamos traducir aproximadamente como "Buscar primero a lo ancho". Esta noción da la idea de **cómo** se recorre el grafo en esta técnica: Se trata de "ir expandiendo" la exploración de los nodos del grafo, en "todas las direcciones a la vez". De esta forma, el grafo se irá recorriendo en orden de **distancia** al nodo origen, formandose una suerte de "onda expansiva" a su alrededor.
-BFS es una técnica para **recorrer** un [[algoritmos-oia:grafos|grafo]], a partir de **un nodo origen**. Proviene de la sigla en inglés "Breadth First Search", que podríamos traducir aproximadamente como "Buscar primero a lo ancho". Esta noción da la idea de **cómo** se recorre el grafo en esta técnica: Se trata de "ir expandiendo" la exploración de los nodos del grafo, en "todas las direcciones a la vez". De esta forma, el grafo se irá recorriendo en orden de **distancia** al nodo origen, formandose una suerte de "onda expansiva" a su alrededor:
 Por ejemplo, sobre el siguiente grafo:
@@ Línea 26: / Línea 24: @@
   * Se comienza inicialmente **con el nodo origen, como único nodo rosa** recién descubierto.
-  * La exploración se expande, **desde los nodos rosa** recién descubiertos, descubriendo nuevos nodos **que no habían sido visitado antes**. Es decir, todos los nodos **blancos** (que nunca habían sido vistos) que resultan ser vecinos de los nodos rosa, **serán los rosa del próximo paso**.
+  * La exploración se expande, **desde los nodos rosa** recién descubiertos, descubriendo nuevos nodos **que no habían sido visitados antes**. Es decir, todos los nodos **blancos** (que nunca habían sido vistos) que resultan ser vecinos de los nodos rosa, **serán los rosa del próximo paso**.
   * El paso anterior se repite una y otra vez descubriendo más y más nodos en orden, hasta que en algún paso ya no se descubran nodos nuevos. Es decir, **se termina el algoritmo cuando ya no hay ningún nodo rosa**.
-[pendiente de acomodar]
+Con esto en mente, podemos dar una implementación del algoritmo. La siguiente implementación asume que los nodos están representados con números de $0$ a $N-1$, que es lo más común, pero las ideas principales no cambian de no ser así.
-, es decir, miramos desde un nodo actual a **todos sus vecinos**, explorando **todas las direcciones a la vez**. Los agregamos a la lista de "nodos que tenemos que mirar", y eliminamos de la lista al nodo actual, marcando que ya lo vimos (si no podemos entrar en un loop y mirar muchas veces los mismos nodos).
+<code cpp>
+int origen = 0; // Podria ser otro nodo, se indica aqui
+vector<bool> visitado(N, false); // Todos los nodos inician blancos, sin visitar
+visitado[origen] = true;
+vector<int> rosasActuales = {origen};
+while (!rosasActuales.empty())
+{
+    vector<int> rosasProximos;
+    for (int nodo : rosasActuales)
+        // ****** para cada vecino de nodo:  ******
+            if (!visitado[vecino])
+            {
+                visitado[vecino] = true;
+                rosasProximos.push_back(vecino);
+            }
+    rosasActuales = rosasProximos;
+}
+</code>
+Como podemos observar, la implementación tiene una parte sin resolver, representada con un comentario: recorrer los vecinos de un nodo dado. La implementación de esa parte dependerá necesariamente de la [[algoritmos-oia:grafos#representacion_en_la_computadora|representación]] que utilicemos.
+Si tenemos el grafo dado como matriz de adyacencia, si $g$ es la matriz de adyacencia (que tiene un 1 en $i,j$ cuando existe arista que va desde $i$ hasta $j$), los vecinos podrían recorrerse de la siguiente manera:
+<code cpp>
+for (int vecino = 0; vecino < n; vecino++)
+if (g[nodo][vecino])
+{
+    ... // Procesar dentro del algoritmo
+}
+</code>
+Si el grafo estuviera representado en cambio mediante listas de adyacencia, almacenadas en el arreglo $g$ de manera tal que $g[i]$ es la lista de adyacencia del nodo $i$, el mismo código lo escribiríamos de la siguiente manera:
+<code cpp>
+for (int vecino : g[nodo])
+{
+    ... // Procesar dentro del algoritmo
+}
+</code>
+Si tuvieramos un ejemplo en el cual el grafo fuera un grafo implícito, correspondiente por ejemplo a una [[algoritmos-oia:grafos:bfs:distintas-movidas-en-tablero|grilla con movimientos codificados]] en arreglos ''dx'' y ''dy'', se harían las cuentas correspondientes para obtener y recorrer todos los vecinos.
+Como vemos, el único cambio ocurre en la parte del código donde exploramos los **vecinos** de un nodo: sin importar cómo hayamos resuelto esa parte, todo el resto del algoritmo queda igual.
+Si ejecutamos el algoritmo anterior sobre el grafo del ejemplo, empezando con el nodo marcado como $E$, y hacemos que el programa muestre cuáles son los valores contenidos en rosasActuales en cada paso, se obtendría una salida como la siguiente (un paso por línea):
+<code cpp>
+    E
+    B C G
+    A D F
+    I H
+</code>
+Que se corresponde con los dibujos anteriores.
+Como comentario final, vale la pena destacar que si bien hemos utilizado fundamentalmente grafos no dirigidos en la explicación, absolutamente todo lo anterior (y todo lo mencionado en este artículo de BFS) funciona perfectamente con grafos dirigidos: el único cuidado que se debe tener es al recorrer los **vecinos** de un nodo, ya que más que "vecinos" serán "sucesores": Si la arista es $u \rightarrow v$, debemos considerar $v$ entre los vecinos de $u$, pero no considerar a $u$ entre los vecinos de $v$ (a menos que por supuesto, también haya otra arista $v \rightarrow u$).
+===== Cálculo de distancias =====
+Notemos que el orden dentro de cada "bolsa" o "capa" de nodos rosa puede variar dependiendo del orden exacto en el que se vayan recorriendo los vecinos en el algoritmo, pero el orden entre "capas" de la "onda expansiva" no: Primero se recorren todos los nodos a **un paso de distancia** del origen, en la siguiente bolsa quedan todos los nodos que están a **dos aristas** de distancia del origen, y así siguiendo.
+Esta observación permite utilizar el algoritmo de BFS anterior para calcular las distancias **desde el origen hasta todos los demás nodos**: La primera capa de "rosasActuales" corresponde a distancia 0 (será únicamente el nodo origen). La segunda corresponde a distancia 1, y así siguiendo. Si se mantiene un contador de distancia que comience en 0, y se incremente luego de cada paso, los nodos de la bolsa de ''rosasActuales'' siempre son los que están a la distancia actual indicada por el contador.
+A continuación se muestra una modificación a la implementación anterior, que calcula distancias usando la idea que hemos mencionado (con las líneas nuevas indicadas):
+<code cpp>
+int origen = 0;
+vector<bool> visitado(N, false);
+vector<int> distancia(N, INFINITO); // Linea NUEVA
+visitado[origen] = true;
+vector<int> rosasActuales = {origen};
+int distanciaActual = 0; // Linea NUEVA
+while (!rosasActuales.empty())
+{
+    for (int x : rosasActuales) // Linea NUEVA
+        distancia[x] = distanciaActual; // Linea NUEVA
+    vector<int> rosasProximos;
+    for (int nodo : rosasActuales)
+        // ****** para cada vecino de nodo:  ******
+            if (!visitado[vecino])
+            {
+                visitado[vecino] = true;
+                rosasProximos.push_back(vecino);
+            }
+    rosasActuales = rosasProximos;
+    distanciaActual++; // Linea NUEVA
+}
+</code>
+Este es un buen momento para mencionar algo que hemos pasado por alto intencionalmente hasta ahora, pero que se relaciona con un detalle del código que acabamos de escribir: la inicialización de las distancias en ''INFINITO''. ¿Por qué hemos hecho eso? Según la [[algoritmos-oia:grafos:definiciones|definición]] usual que se usa para la distancia, cuando **no existe camino** desde un nodo $a$ hasta un nodo $b$, se dice que la distancia $d(a,b) = +\infty$. Lo que hasta ahora venimos asumiendo es que el grafo es conexo. Particularmente, venimos suponiendo que desde el nodo origen es posible alcanzar **todos** los nodos del grafo, pero esto no tiene por qué ser así. El algoritmo de BFS tiene la propiedad de alcanzar en su expansión a todos aquellos nodos que son **alcanzables desde el nodo origen**: si existe algún camino desde el origen hasta un cierto nodo $x$, entonces el algoritmo de BFS comenzando en dicho origen, encontrará en algún momento al nodo $x$.
+Los nodos que quedan sin encontrar nunca entonces son los no alcanzables, y por lo tanto su distancia es infinito. Con lo cual, es adecuado nuestro valor de inicialización: ponemos todo en infinito, y para aquellos que sean encontrados, la distancia será reemplazada por la distancia verdadera, y quedarán en infinito exactamente los que BFS no recorra, que son aquellos de verdad imposibles de alcanzar.
+Si quisiéramos recorrer **todo** el grafo (por ejemplo, para contar componentes conexas de un grafo no dirigido), lo que podemos hacer generalmente es un for que itere todos los nodos, y cada vez que encuentre un nodo que aún no fue nunca visitado, lance una exploración de BFS nueva con origen en ese nodo, la cual recorrerá todos los alcanzables desde él.
+===== Cálculo de caminos mínimos =====
+Se suele decir que BFS es un algoritmo "de camino mínimo", puesto que permite calcular caminos de mínima longitud **desde un origen**, hasta **todos los demás** nodos.
+Ya hemos visto de hecho cómo calcular las distancias, es decir, las **longitudes** de esos caminos mínimos. Pero nos faltaría saber cómo calcular los caminos mínimos en sí.
+La forma ideal de representar los caminos en BFS es mediante un [[algoritmos-oia:grafos:arboles|árbol]] particular: concretamente, un árbol [[algoritmos-oia:grafos:definiciones|con raíz]] en el nodo origen. El árbol así formado es un [[algoritmos-oia:grafos:dag-caminos-minimos|árbol de caminos mínimos]]: un camino mínimo desde el origen hasta un nodo cualquiera, se obtendrá (en orden inverso) siguiendo el camino en el árbol desde el nodo objetivo hasta la raíz.
+La forma de generar este árbol es manteniendo para cada nodo, su **padre** en el árbol de caminos mínimos. Este nodo padre será el nodo rosa **a través del cuál fue descubierto**. Pensemos en términos de las "capas" de distancia de la onda expansiva: un nodo a distancia 2, se descubre (se vuelve un nodo rosa) gracias a que es encontrado al explorar los vecinos de un nodo a distancia 1 (pues una capa descubre la siguiente). Si vamos recorriendo un camino hacia atrás, **que siempre baje en uno** la distancia al origen, sin dudas el camino en cuestión será mínimo. Eso es lo que se hace al guardar el "padre" de cada nodo: se guarda a qué nodo se debe ir a continuación, para acercarse estrictamente al origen.
+De esta manera, una vez completada la ejecución y teniendo todos los padres, para formar el camino desde el origen hasta un cierto nodo, se comienza por el final: a partir del nodo destino, vamos viendo "de dónde se vino", siguiendo los "padres" en el árbol hasta dar con el comienzo. De esta forma se reconstruye un camino óptimo "marcha atrás".
+A continuación se muestra un árbol de caminos mínimos para el ejemplo anterior (para un recorrido comenzando en el nodo $E$):
+{{ :algoritmos-oia:grafos:bfs:bfsarbolcaminos.png?nolink |}}
+En este caso, este no es el único árbol de caminos mínimos posible: El nodo $D$, que está a distancia 2, se puede descubrir "2 veces" desde la capa anterior: desde el nodo $C$, y desde el nodo $G$. El árbol del ejemplo corresponde al caso en que $C$ ha sido procesado antes que $G$, de manera que $D$ fue marcado como un nodo rosa para el siguiente paso **desde $C$**, y por lo tanto $C$ queda como padre de $D$ en este caso. Si los vecinos de los nodos se recorrieran en un orden diferente, de tal forma que $G$ fuera procesado primero, el padre de $D$ hubiera sido en su lugar el nodo $G$. Si bien el algoritmo se queda con uno de estos árboles arbitrario, en cualquier caso los caminos obtenidos son óptimos, pues en ambos casos se ve que en "2 saltos" se llega al origen $E$.
+Para finalizar, mostramos el código para generar los padres de cada nodo (hemos eliminado en esta versión el cálculo de distancias, pero indudablemente se podría dejar como antes si quisiéramos):
+<code cpp>
+int origen = 0;
+vector<bool> visitado(N, false);
+vector<int> padre(N, -1); // Linea NUEVA: -1 seria no tener padre: el origen, o los inalcanzables
+visitado[origen] = true;
+vector<int> rosasActuales = {origen};
+while (!rosasActuales.empty())
+{
+    vector<int> rosasProximos;
+    for (int nodo : rosasActuales)
+        // ****** para cada vecino de nodo:  ******
+            if (!visitado[vecino])
+            {
+                visitado[vecino] = true;
+                rosasProximos.push_back(vecino);
+                padre[vecino] = nodo; // Linea NUEVA
+            }
+    rosasActuales = rosasProximos;
+}
+</code>
+Como se puede apreciar, el mecanismo es sencillísimo: basta agregar una línea cuando se descubre un nodo nuevo, anotando como padre al nodo desde el cuál fue descubierto.
+Al final, se puede reconstruir el camino marcha atrás, moviéndose al padre hasta caer en el valor especial "-1", que hemos usado para indicar que no hay padre.
+===== Complejidad =====
+Suponiendo que explorar los vecinos de un nodo tiene un costo proporcional a su grado (por ejemplo, como ocurre al usar listas de adyacencia), todas estas versiones del algoritmo tienen una complejidad $O(n+m)$.
+Esto es porque cada nodo es procesado cuando es rosa, y un nodo es rosa durante **únicamente un paso**. Por lo tanto, se trabaja con un nodo explorando sus vecinos **una única vez** en todo el algoritmo. Si explorar los vecinos de un nodo cuesta proporcional a su grado, el costo total del algoritmo, además de un $O(n)$ fijo para crear el arreglo de visitados y similares estructuras, tendrá un costo igual a la suma de todos los grados, que es $2m$. Por lo tanto el total es $O(n+m)$, proporcional al total de nodos y ejes del grafo, lo cual es muy bueno.
+Si se utilizara matriz de adyacencia, el costo de buscar los vecinos de un nodo sería siempre $O(n)$, sin importar su grado. En este caso, el costo de explorar cada uno de los $n$ nodos sería siempre $n$, y en total el costo sería $O(n^2)$. Muchas veces es perfectamente razonable un costo de $O(n^2)$, y en estos casos se puede utilizar perfectamente BFS con matriz de adyacencia.
+===== Implementación con cola =====
+Si bien la idea fundamental del algoritmo de BFS se basa en este recorrido en "capas", estilo onda expansiva desde un origen, la implementación más común del algoritmo es una que procesa nodo por nodo, sin hacer la "separación en capas" explícitamente. Esta implementación es un poco más corta y más directa, pero es menos evidente el funcionamiento del algoritmo porque la capa actual con la siguiente se encuentran siempre mezcladas en una única cola: esta cola tiene los elementos de la capa actual al comienzo, y los de la capa siguiente van todos al final.
+FIXME: Revisar y acomodar esta parte, que está escrita menos detalladamente que la anterior
 Su implementación es muy sencilla:

OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página