Introducción En la , vimos cómo resolver el problema de la ruta más corta de todos los pares utilizando el . También exploramos varias formas de mejorar el rendimiento del algoritmo mediante el uso del paralelismo y la vectorización. publicación anterior algoritmo Floyd-Warshall Sin embargo, si piensas en los resultados del algoritmo Floyd-Warshall, te darás cuenta rápidamente del momento interesante: conocemos las distancias (valores de los caminos más cortos) entre los vértices de un gráfico, pero no conocemos las "rutas", es decir, no sabemos qué vértices contribuyen a cada camino más corto y no podemos reconstruir estas "rutas" a partir de los resultados que tenemos. En este artículo, los invito a que me acompañen y amplíen el algoritmo Floyd-Warshall. Esta vez, nos aseguraremos de poder calcular la distancia y reconstruir la “ruta”. Un poco de teoría conocida… Antes de sumergirnos en el código y los puntos de referencia, revisemos una teoría sobre cómo funciona el algoritmo Floyd-Warshall. A continuación se muestra una descripción textual del algoritmo: Comenzamos representando un grafo ( ) de tamaño como una matriz ( ) de tamaño donde cada celda contiene el peso de una arista desde el vértice hasta el vértice (ver Figura 1). En los casos en los que no hay aristas entre vértices, la celda se establece en un valor especial (mostrado como celdas oscuras en la Figura 1). G N W N x N W[i,j] i j NO_EDGE A partir de ahora, decimos: contiene una distancia entre los vértices y . W[i,j] i j A continuación, tomamos un vértice e iteramos a través de todos los pares de vértices verificando si la distancia es menor que la distancia actualmente conocida entre y . k W[i,j] i ⭢ k ⭢ j i j El valor más pequeño se almacena en y el paso n.° 3 se repite para los siguientes hasta que todos los vértices de se hayan utilizado como . W[i,j] k G k Aquí está el pseudocódigo: algorithm FloydWarshall(W) do for k = 0 to N - 1 do for i = 0 to N - 1 do for j = 0 to N - 1 do W[i,j] = min(W[i,j], W[i,k] + W[k,j]) end for end for end for end algorithm Una vez terminado, cada celda de la matriz contendrá una distancia de la ruta más corta entre los vértices y o un valor , si no hay una ruta entre ellos. W[i,j] W i j NO_EDGE Como mencioné al principio, tener solo esta información hace que sea imposible reconstruir las rutas entre estos vértices. Entonces… ¿qué deberíamos hacer para poder reconstruir estas rutas? Bueno… puede que suene obvio pero… ¡necesitamos recopilar más datos! …Un poco de la misma teoría pero desde un ángulo diferente La esencia del algoritmo Floyd-Warshall es un compartimento de distancia conocida con una distancia de camino potencialmente nuevo de a a través del vértice intermedio . W[i,j] i j k Le presto tanta atención a este detalle porque es la clave para preservar la información de la ruta. Tomemos el gráfico anterior de 5 vértices (ver Imagen 2) y ejecutemos el algoritmo Floyd-Warshall en él. Inicialmente, conocemos todos los bordes del gráfico, lo que nos da las siguientes rutas: , , , , y . 0 ⭢ 1 :2 0 ⭢ 4 :10 1 ⭢ 3 :1 2 ⭢ 4 :1 3 ⭢ 2 :1 3 ⭢ 4 :3 Utilizo el formato “desde” ⭢ “hasta” :”distancia” del para escribir rutas. post anterior - Nota del autor También sabemos que no hay aristas que conduzcan al vértice , por lo que ejecutar un algoritmo para no tiene sentido. También es obvio que hay una única arista ( ) que conduce desde el vértice al vértice , lo que también hace que la ejecución de todos (la es "desde" aquí) no tenga sentido y, como el vértice tiene aristas con y , tampoco tiene sentido ejecutar algoritmos para ningún que no sea o (la es "hasta" aquí). 0 k = 0 0 ⭢ 1 0 1 i != 0 i 1 2 4 j 2 4 j Es por eso que nuestro primer paso será ejecutar un algoritmo para , y . k = 1 i = 0 j = 2,4 Paso Camino Comentario 1 0 ⭢ 1 ⭢ 2 Camino encontrado. Distancia = 3 (no era nada) 2 0 ⭢ 1 ⭢ 4 Ruta encontrada. Distancia = 8 (era 10). Hemos encontrado dos caminos: un nuevo camino ( ) y un atajo ( ). Ambos pasan por el vértice . Si no almacenamos esta información (el hecho de que llegamos a y a través de ) en algún lugar ahora mismo, se perderá para siempre (y eso es todo lo contrario de lo que queremos). 0 ⭢ 1 ⭢ 2 0 ⭢ 1 ⭢ 4 1 2 4 1 ¿Qué debemos hacer entonces? Actualizaremos la matriz con los nuevos valores (ver Imagen 3a) y también almacenaremos el valor de (que es ) en las celdas y de una nueva matriz del mismo tamaño que la matriz pero inicializada con valores (ver Imagen 3b). W k k = 1 R[0,2] R[0,4] R W NO_EDGE Por ahora, no te concentres en qué es exactamente la matriz Sigamos adelante y ejecutemos el algoritmo para el próximo . R k = 2 Aquí, haremos el mismo análisis (para entender qué combinaciones tienen sentido ejecutar) que hicimos para pero esta vez, utilizaremos la matriz en lugar del gráfico Observa la matriz , especialmente en la columna n.° 2 y la fila n.° 2 (Imagen 4). k = 1, W G W Aquí se puede ver que hay dos caminos al vértice desde el vértice y desde el vértice (columna n.° 2), y dos caminos desde el vértice al vértice y al vértice (fila n.° 2). Sabiendo esto, tiene sentido ejecutar el algoritmo solo para combinaciones de , y . 2 0 1 2 3 4 k = 2 i = 0,1 j = 3,4 Paso Camino Comentario 1 0 ⭢ 2 ⭢ 3 Ruta encontrada. Distancia = 4 (no era nada) 2 0 ⭢ 2 ⭢ 4 Ruta encontrada. Distancia = 6 (antes 8) 3 1 ⭢ 2 ⭢ 3 Ruta encontrada. Distancia = 2 (no era nada) 4 1 ⭢ 2 ⭢ 4 Ruta encontrada. Distancia = 4 (antes 6) Como ya hemos hecho anteriormente, estamos actualizando las celdas , , , con nuevas distancias y las celdas , , y con (ver Figura 5). W[0,3] W[0,4] W[1,3] W[1,4] R[0,3] R[0,4] R[1,3] R[1,4] k = 2 Sólo queda para procesar (porque no hay aristas que conduzcan desde el vértice a ningún otro vértice en el gráfico). k = 3 4 Nuevamente, echemos un vistazo a la matriz (Imagen 6). W Según la matriz , hay tres caminos al vértice desde los vértices , y (columna n.° 3), y hay un camino desde el vértice hasta el vértice (fila n.° 3). Por lo tanto, tenemos los siguientes caminos para procesar: W 3 0 1 2 3 4 Paso Camino Comentario 1 0 ⭢ 3 ⭢ 4 Ruta encontrada. Distancia = 5 (antes 6) 2 1 ⭢ 3 ⭢ 4 Ruta encontrada. Distancia = 3 (antes 4) 3 2 ⭢ 3 ⭢ 4 Ruta encontrada. Distancia = 2 (antes 3) Esta fue la última iteración del algoritmo. Solo falta actualizar las celdas , , con las nuevas distancias y establecer las celdas , , en . W[0,4] W[1,4] W[2,4] R[0,4] R[1,4] R[2,4] 3 Esto es lo que tenemos al final del algoritmo (Imagen 7). Como sabemos por la , la matriz ahora contiene todos los pares de caminos más cortos en el grafo Pero, ¿qué se almacena dentro de la matriz ? publicación anterior W G R Regreso Cada vez que encontrábamos un nuevo camino más corto, actualizábamos la celda correspondiente de la matriz con el valor actual de . Si bien, al principio, esta acción puede parecer misteriosa, tiene un significado muy simple: estábamos almacenando el vértice desde el cual llegamos al vértice de destino: (aquí llegamos a directamente desde ). R k i ⭢ k ⭢ j j k Este momento es crucial, porque conocer el vértice del que venimos nos permite reconstruir la ruta moviéndonos hacia atrás (como una langosta) desde el vértice (el “hacia”) hasta el vértice (el “desde”). j i A continuación se muestra una descripción textual del algoritmo para reconstruir la ruta de a : i j Preparar la matriz dinámica vacía X Comience leyendo un valor de la celda . z R[i,j] Si es , entonces se encuentra la ruta de a y debemos continuar con el paso n.° 7. z NO_EDGE i j Anteponga a una matriz dinámica z X Leer el valor de la celda en . R[i,z] z Repita los pasos 3, 4 y 5 hasta que se alcance la condición de salida en 3. Anteponer a X. i Añade a j X Ahora la matriz dinámica contiene la ruta de a . X i j Tenga en cuenta que el algoritmo anterior solo funciona con rutas existentes. Tampoco es perfecto desde el punto de vista del rendimiento y, sin duda, se puede optimizar. Sin embargo, en el marco de esta publicación, se describe específicamente de tal manera que sea más fácil de entender y reproducir en una hoja de papel. - Nota del autor En pseudocódigo, parece aún más sencillo: algorithm RebuildRoute(i, j, R) x = array() z = R[i,j] while (z ne NO_EDGE) do x.prepend(z) z = R[i,z] end while x.prepend(i) x.append(j) return x end algorithm Probémoslo en nuestro gráfico y reconstruyamos una ruta desde el vértice al vértice (ver Imagen 8). G 0 4 A continuación se muestra una descripción textual de la ilustración anterior: Comenzamos leyendo el valor de , que da como resultado . Según el algoritmo, esto significa que la ruta va al vértice desde el vértice (mostrado en AZUL). R[0,4] 3 4 3 Como el valor de no es , procedemos y leemos el valor de que da como resultado (mostrado en VERDE). R[0,4] NO_EDGE R[0,3] 2 Nuevamente, debido a que el valor de no es , procedemos y leemos el valor de que resulta en (mostrado en ROJO). R[0,3] NO_EDGE R[0,2] 1 Por último, leemos un valor de , que da como resultado el valor , es decir, no hay más vértices excepto y que contribuyan a la ruta. Por lo tanto, la ruta resultante es: que si observamos el gráfico efectivamente corresponde al camino más corto desde el vértice al vértice . R[0,1] NO_EDGE 0 4 0 ⭢ 1 ⭢ 2 ⭢ 3 ⭢ 4 0 4 Un lector atento podría preguntar: ¿Cómo podemos estar seguros de que todos los datos que leemos de la matriz pertenecen a la misma ruta? R - Lector reflexivo Es una muy buena pregunta. Estamos seguros porque actualizamos la matriz con un nuevo valor cuando actualizamos el valor de la ruta más corta en la matriz Por lo tanto, al final, cada fila de la matriz contiene datos relacionados con las rutas más cortas. Ni más ni menos. R W R Ahora que hemos terminado con la teoría, es hora de implementarla. Implementación en C# En el , además de implementar una versión original del algoritmo Floyd-Warshall, también integramos varias optimizaciones: soporte para gráficos dispersos, paralelismo y vectorización, y al final también las combinamos todas. post anterior No hay razón para repetir todo esto hoy. Sin embargo, me gustaría mostrarles cómo integrar la memorización de rutas en las versiones originales y vectorizadas (con soporte para gráficos dispersos) del algoritmo. Integración en el algoritmo original Puede resultar difícil de creer, pero para integrar la memorización de rutas en la versión original de los algoritmos, todo lo que tenemos que hacer es: Ampliar la firma de la función para incluir la matriz como un parámetro separado – . R int[] routes Guardar k en cada vez que se cambia la ruta más corta (líneas: 2 y 14). routes Eso es todo. Sólo una línea y media de código: public void BaselineWithRoutes( int[] matrix, int[] routes, int sz) { for (var k = 0; k < sz; ++k) { for (var i = 0; i < sz; ++i) { for (var j = 0; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; routes[i * sz + j] = k; } } } } } Integración en algoritmo vectorizado La integración en una versión vectorizada (con soporte para gráficos dispersos) requiere un poco más de esfuerzo para completarse, sin embargo, los pasos conceptuales son los mismos: Ampliar la firma de la función para incluir la matriz como un parámetro separado – . R int[] routes En cada iteración, inicialice un nuevo vector de valores (línea: 6). k Guardar el vector de valores en cada vez que se cambia la ruta más corta (líneas: 31-32). k routes Actualice una parte no vectorizada del algoritmo de la misma manera que actualizamos el algoritmo original (línea: 41). public void SpartialVectorOptimisationsWithRoutes( int[] matrix, int[] routes, int sz) { for (var k = 0; k < sz; ++k) { var k_vec = new Vector<int>(k); for (var i = 0; i < sz; ++i) { if (matrix[i * sz + k] == Constants.NO_EDGE) { continue; } var ik_vec = new Vector<int>(matrix[i * sz + k]); var j = 0; for (; j < sz - Vector<int>.Count; j += Vector<int>.Count) { var ij_vec = new Vector<int>(matrix, i * sz + j); var ikj_vec = new Vector<int>(matrix, k * sz + j) + ik_vec; var lt_vec = Vector.LessThan(ij_vec, ikj_vec); if (lt_vec == new Vector<int>(-1)) { continue; } var r_vec = Vector.ConditionalSelect(lt_vec, ij_vec, ikj_vec); r_vec.CopyTo(matrix, i * sz + j); var ro_vec = new Vector<int>(routes, i * sz + j); var rk_vec = Vector.ConditionalSelect(lt_vec, ro_vec, k_vec); rk_vec.CopyTo(routes, i * sz + j); } for (; j < sz; ++j) { var distance = matrix[i * sz + k] + matrix[k * sz + j]; if (matrix[i * sz + j] > distance) { matrix[i * sz + j] = distance; routes[i * sz + j] = k; } } } } } Un pequeño recordatorio: la operación devuelve un nuevo vector donde los valores son iguales al menor de dos valores correspondientes de los vectores de entrada, es decir, si el valor del vector es igual a , entonces la operación selecciona un valor de ; de lo contrario, selecciona un valor de . Vector.ConditionalSelect lt_vec -1 ij_vec k_vec - Nota del autor Evaluación comparativa Recopilar información de rutas parece bastante razonable porque... ¿por qué no? Especialmente cuando es tan fácil de integrar en algoritmos existentes. Sin embargo, veamos qué tan práctico es integrarlo de manera predeterminada. A continuación se muestran dos conjuntos de pruebas comparativas: con y sin algoritmo (ambos ejecutan versiones originales y vectorizadas del algoritmo). Todas las pruebas comparativas se ejecutaron con v0.13.1 (.NET 6.0.4 x64) en una máquina equipada con un procesador Intel Core i5-6200U CPU 2.30GHz (Skylake) y con Windows 10. BenchmarkDotNet Todos los experimentos se ejecutaron en el conjunto predefinido de gráficos utilizados en la : 300, 600, 1200, 2400 y 4800 vértices. publicación anterior El código fuente y los gráficos experimentales están disponibles en el repositorio de GitHub. Los gráficos experimentales se pueden encontrar en el directorio . el archivo Data/Sparse-Graphs.zip Todos los puntos de referencia de esta publicación se implementan en APSP02.cs . A continuación se muestran los resultados de referencia donde los métodos y corresponden a la versión original del algoritmo y los métodos y corresponden a una versión vectorizada (con soporte para gráficos dispersos) del algoritmo. Baseline BaselineWithRoutes SpartialVectorOptimisations SpartialVectorOptimisationsWithRoutes Método Tamaño Media (ms) Error (ms) Desviación estándar (ms) Base 300 40.233 0,0572 0,0477 Línea base con rutas 300 40.349 0,1284 0,1201 Optimizaciones de vectores parciales 300 4.472 0,0168 0,0140 Optimizaciones de vectores parciales con rutas 300 4.517 0,0218 0,0193 Base 600 324.637 5.6161 4.6897 Línea base con rutas 600 321.173 1.4339 1.2711 Optimizaciones de vectores parciales 600 32.133 0,2151 0,1679 Optimizaciones de vectores parciales con rutas 600 34.646 0,1286 0,1073 Base 1200 2.656.024 6.9640 5.8153 Línea base con rutas 1200 2.657.883 8.8814 7.4164 Optimizaciones de vectores parciales 1200 361.435 2.5877 2.2940 Optimizaciones de vectores parciales con rutas 1200 381.625 3.6975 3.2777 Base 2400 21.059.519 38.2291 33.8891 Línea base con rutas 2400 20.954.852 56.4719 50.0609 Optimizaciones de vectores parciales 2400 3.029.488 12.1528 11.3677 Optimizaciones de vectores parciales con rutas 2400 3.079.006 8.6125 7.1918 Base 4800 164.869.803 547.6675 427.5828 Línea base con rutas 4800 184.305.980 210.9535 164.6986 Optimizaciones de vectores parciales 4800 21.882.379 200.2820 177.5448 Optimizaciones de vectores parciales con rutas 4800 21.004.612 79.8752 70.8073 Los resultados de las pruebas comparativas no son fáciles de interpretar. Si los analizamos con más detenimiento, encontraremos una combinación en la que la recopilación de rutas hizo que el algoritmo se ejecutara más rápido o sin ningún efecto significativo. Esto parece muy confuso (y si lo es, te recomiendo encarecidamente que escuches este con y para comprender mejor qué cosas complicadas pueden afectar las mediciones). Mi mejor interpretación aquí es que el comportamiento "confuso" es causado por un gran rendimiento de la caché de la CPU (porque los gráficos no son lo suficientemente grandes como para saturar las cachés). En parte, esta teoría se basa en la muestra " ", donde podemos ver una degradación significativa en el gráfico más grande. Sin embargo, no lo verifiqué. programa Denis Bakhvalov Andrey Akinshin negrita En general, el punto de referencia muestra que si no estamos hablando de escenarios de rendimiento extremadamente alto y gráficos enormes, está bien integrar la memorización de rutas en ambos algoritmos de forma predeterminada (pero tenga en cuenta que duplicará el consumo de memoria porque necesitamos asignar dos matrices y en lugar de una). W R Lo único que queda es una implementación del algoritmo de reconstrucción de ruta. Implementación del algoritmo de reconstrucción de ruta La implementación de algoritmos de reconstrucción de rutas en C# es sencilla y refleja casi por completo el pseudocódigo demostrado anteriormente (usamos para representar una matriz dinámica): LinkedList<T> public static IEnumerable<int> RebuildWithLinkedList( int[] routes, int sz, int i, int j) { var x = new LinkedList<int>(); var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x.AddFirst(z); z = routes[i * sz + z]; } x.AddFirst(i); x.AddLast(j); return x; } El algoritmo anterior no es perfecto y definitivamente se puede mejorar. La mejora más simple que podemos hacer es preasignar una matriz de tamaño y completarla en orden inverso: sz public static IEnumerable<int> RebuildWithArray( int[] routes, int sz, int i, int j) { var x = new int[sz]; var y = sz - 1; // Fill array from the end x[y--] = j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { x[y--] = z; z = routes[i * sz + z]; } x[y] = i; // Create an array segment from 'y' to the end of the array // // This is required because 'sz' (and therefore length of the array x) // equals to the number of vertices in the graph // // So, in cases when route doesn't span through // all vertices - we need return a segment of the array return new ArraySegment<int>(x, y, sz - y); } Si bien esta “optimización” reduce el número de asignaciones a una, no necesariamente hace que el algoritmo sea “más rápido” o “asigne menos memoria” que el anterior. El punto aquí es que si necesitamos tener una ruta ordenada de a , siempre tendremos que “invertir” los datos que recuperamos de la matriz , y no hay forma de escapar de esto. i j R Pero si podemos presentar datos en orden inverso, entonces podemos utilizar LINQ y evitar asignaciones innecesarias: public static IEnumerable<int> RebuildWithReverseYield( int[] routes, int sz, int i, int j) { yield return j; var z = routes[i * sz + j]; while (z != Constants.NO_EDGE) { yield return z; z = routes[i * sz + z]; } yield return i; } Puede haber muchas más variantes de cómo se puede “cambiar” o “mejorar” este código. Lo importante aquí es recordar que cualquier “cambio” tiene desventajas en términos de memoria o ciclos de CPU. ¡Sientete libre de experimentar! ¡Las posibilidades son casi ilimitadas! Puede encontrar implementaciones de todos los algoritmos de ruta en GitHub en el archivo Routes.cs . Conclusión En este artículo, profundizamos en la teoría detrás del algoritmo Floyd-Warshall y lo ampliamos con la posibilidad de memorizar las rutas más cortas. Luego, actualizamos las implementaciones de C# (originales y vectorizadas) del . Al final, implementamos algunas versiones del algoritmo para reconstruir las rutas. artículo anterior Hemos repetido mucho, pero al mismo tiempo espero que hayas encontrado algo nuevo e interesante en este. Este no es el final del problema de los caminos más cortos de todos los pares. Es solo el comienzo. Espero que hayas disfrutado la lectura ¡y hasta la próxima!
