En teoría de grafos, un árbol de expansión mínimo (MST)de una gráfica con y es un subgrafo de árbol de que contiene todos sus vértices y tiene un peso mínimo.
Los MST son herramientas útiles y versátiles que se utilizan en una amplia variedad de campos prácticos y teóricos. Por ejemplo, una empresa que busca abastecer a varias tiendas con un determinado producto de un solo almacén puede utilizar un MST que se origina en el almacén para calcular las rutas más cortas a cada tienda de la empresa. En este caso, las tiendas y el almacén se representan como vértices y las conexiones viales entre ellos, como bordes. Cada borde está etiquetado con la longitud de la conexión vial correspondiente.
Si no tiene los bordes ponderados, todos los árboles de expansión poseen el mismo número de bordes y, por lo tanto, el mismo peso. En el caso de los bordes ponderados , el árbol de expansión, cuya suma de los pesos de los bordes es el más bajo entre todos los árboles de expansión de, se denomina árbol de expansión mínimo (MST). No es necesariamente único. De manera más general, los gráficos que no están necesariamente conectados tienen bosques de expansión mínimos , que consisten en una unión de MST para cada componente conectado .
Como encontrar MST es un problema generalizado en la teoría de grafos, existen muchos algoritmos secuenciales para resolverlo. Entre ellos se encuentran los algoritmos de Prim , Kruskal y Borůvka , cada uno de los cuales utiliza diferentes propiedades de los MST. Todos operan de manera similar: un subconjunto decrece iterativamente hasta que se descubre un MST válido. Sin embargo, como los problemas prácticos suelen ser bastante grandes (las redes de carreteras a veces tienen miles de millones de bordes), el rendimiento es un factor clave. Una de las opciones de mejora es por parallelising conocidos algoritmos MST . [1]
Algoritmo de Prim
Este algoritmo utiliza la propiedad de corte de los MST. A continuación se proporciona una implementación simple de pseudocódigo de alto nivel:
dónde es un vértice aleatorio en repetir veces encontrar el borde más ligero S t pero volver T
Cada borde se observa exactamente dos veces, es decir, al examinar cada uno de sus puntos finales. Cada vértice se examina exactamente una vez para un total deoperaciones aparte de la selección del borde más ligero en cada iteración del bucle. Esta selección a menudo se realiza mediante una cola de prioridad (PQ). Para cada flanco como máximo una disminución Operación clave ( amortizada en) se realiza y cada iteración de bucle realiza una operación deleteMin (). Por lo tanto, al usar montones de Fibonacci, el tiempo de ejecución total del algoritmo de Prim es asintóticamente en.
Es importante tener en cuenta que el bucle es inherentemente secuencial y no se puede paralelizar correctamente. Este es el caso, ya que el borde más claro con un punto final en y en podría cambiar con la adición de bordes a . Por lo tanto, no se pueden realizar dos selecciones de un borde más ligero al mismo tiempo. Sin embargo, existen algunos intentos de paralelización .
Una posible idea es utilizar procesadores para admitir el acceso PQ en en una máquina EREW-PRAM , [2] reduciendo así el tiempo de ejecución total a.
Algoritmo de Kruskal
El algoritmo MST de Kruskal utiliza la propiedad de ciclo de los MST. A continuación se proporciona una representación de pseudocódigo de alto nivel.
bosque con cada vértice en su propia sub-árbol foreach en orden ascendente de peso si y en diferentes subárboles de volver T
Los subárboles de se almacenan en estructuras de datos de búsqueda de unión , por lo que es posible verificar si dos vértices están o no en el mismo subárbol en amortizado dónde es la función inversa de Ackermann . Por lo tanto, el tiempo de ejecución total del algoritmo está en. Aquí denota la función de Ackermann inversa de un solo valor, para la cual cualquier entrada realista produce un número entero menor que cinco.
Método 1: paralelismo del paso de clasificación
De manera similar al algoritmo de Prim, hay componentes en el enfoque de Kruskal que no pueden ser paralelos en su variante clásica. Por ejemplo, determinar si dos vértices están o no en el mismo subárbol es difícil de paralelizar, ya que dos operaciones de unión pueden intentar unir los mismos subárboles al mismo tiempo. Realmente, la única oportunidad para la paralelización radica en el paso de clasificación. Como la clasificación es lineal en el caso óptimo en procesadores, el tiempo de ejecución total se puede reducir a .
Enfoque 2: Filtro-Kruskal
Otro enfoque sería modificar el algoritmo original aumentando más agresivamente. Esta idea fue presentada por Osipov et al. [3] [4] La idea básica detrás de Filter-Kruskal es dividir los bordes de una manera similar para ordenar rápidamente y filtrar los bordes que conectan los vértices que pertenecen al mismo árbol para reducir el costo de clasificación. A continuación se proporciona una representación de pseudocódigo de alto nivel.
filterKruskal (): si KruskalThreshold: retorno kruskal ( )pivote = elegir aleatorio ( ) , dividir( , pivote) filterKruskal ( ) filtrar( ) filterKruskal ( ) volver dividir( , pivote): para cada : si peso ( ) pivote: demás retorno ( , )filtrar( ): para cada : si encuentra-conjunto (u) conjunto de búsqueda (v): regreso
Filter-Kruskal es más adecuado para la paralelización, ya que la clasificación, la división y el filtrado tienen paralelizaciones intuitivamente fáciles en las que los bordes simplemente se dividen entre los núcleos.
Algoritmo de Borůvka
La idea principal detrás del algoritmo de Borůvka es la contracción de los bordes . Un borde se contrae quitando primero del gráfico y luego redirigir cada borde a . Estos nuevos bordes conservan sus antiguos pesos de borde. Si el objetivo no es solo determinar el peso de un MST, sino también qué aristas comprende, debe tenerse en cuenta entre qué pares de vértices se contrajo una arista. A continuación se presenta una representación de pseudocódigo de alto nivel.
tiempo por más ligero por contrato volver T
Es posible que las contracciones den lugar a múltiples aristas entre un par de vértices. La forma intuitiva de elegir el más ligero de ellos no es posible en. Sin embargo, si todas las contracciones que comparten un vértice se realizan en paralelo, esto es factible. La recursividad se detiene cuando solo queda un vértice, lo que significa que el algoritmo necesita como máximo iteraciones, lo que lleva a un tiempo de ejecución total en .
Paralelización
Una posible paralelización de este algoritmo [5] [6] [7] produce una complejidad de tiempo polilogarítmica , es decir y existe una constante así que eso . Aquí denota el tiempo de ejecución de un gráfico con bordes vértices en una máquina con procesadores. La idea básica es la siguiente:
tiempo encontrar los bordes incidentes más ligeros // asignar el subgrafo correspondiente a cada vértice // contratar cada subgrafo //
El MST entonces consta de todos los bordes más claros encontrados.
Esta paralelización utiliza la representación gráfica de matriz de adyacencia para . Este consta de tres matrices: de longitud para los vértices, de longitud para los puntos finales de cada uno de los bordes y de longitud para los pesos de los bordes. Ahora para el vértice el otro extremo de cada borde incidente a se puede encontrar en las entradas entre y . El peso del-th borde en puede encontrarse en . Entonces el-th borde en está entre vértices y si y solo si y .
Encontrar el borde incidente más ligero
Primero los bordes se distribuyen entre cada uno de los procesadores. La-th procesador recibe los bordes almacenados entre y . Además, cada procesador necesita saber a qué vértice pertenecen estas aristas (ya que solo almacena uno de los puntos finales del borde) y lo almacena en la matriz . Es posible obtener esta información en utilizando búsquedas binarias o en usando una búsqueda lineal. En la práctica, este último enfoque es a veces más rápido, aunque asintóticamente peor.
Ahora cada procesador determina el borde más ligero incidente en cada uno de sus vértices.
encontrar( , ) para Si Si
Aquí surge el problema de que algunos vértices son manejados por más de un procesador. Una posible solución a esto es que cada procesador tiene su propiomatriz que luego se combina con las de los demás mediante una reducción. Cada procesador tiene como máximo dos vértices que también son manejados por otros procesadores y cada reducción está en. Por lo tanto, el tiempo de ejecución total de este paso está en.
Asignar subgrafos a vértices
Observe el gráfico que consta únicamente de los bordes recopilados en el paso anterior. Estos bordes se dirigen lejos del vértice al que son el borde incidente más ligero. El gráfico resultante se descompone en varios componentes débilmente conectados. El objetivo de este paso es asignar a cada vértice el componente del que forma parte. Tenga en cuenta que cada vértice tiene exactamente un borde saliente y, por lo tanto, cada componente es un pseudotárbol, un árbol con un solo borde adicional que corre en paralelo al borde más claro del componente pero en la dirección opuesta. El siguiente código muta este borde adicional en un bucle:
paralelo para todos Si
Ahora, cada componente débilmente conectado es un árbol dirigido donde la raíz tiene un bucle . Esta raíz se elige como representante de cada componente. El siguiente código usa la duplicación para asignar a cada vértice su representante:
tiempo para todos
Ahora cada subgrafo es una estrella . Con algunas técnicas avanzadas, este paso necesita hora.
Contratando los subgrafos
En este paso, cada subgrafo se contrae en un solo vértice.
número de subgrafos encontrar una función biyectiva raíz de estrella
Encontrar la función biyectiva es posible en usando una suma de prefijo. Como ahora tenemos un nuevo conjunto de vértices y aristas, la matriz de adyacencia debe reconstruirse, lo que se puede hacer usando Integersort en en hora.
Complejidad
Cada iteración ahora necesita tiempo y al igual que en el caso secuencial hay interaciones, lo que resulta en un tiempo de ejecución total de . Si la eficiencia del algoritmo está en y es relativamente eficiente. Si entonces es absolutamente eficiente.
Más algoritmos
Hay muchos otros algoritmos paralelos que tratan el problema de encontrar un MST. Con un número lineal de procesadores es posible lograr esto en. [8] [9] Bader y Cong presentaron un algoritmo MST, que era cinco veces más rápido en ocho núcleos que un algoritmo secuencial óptimo. [10]
Otro desafío es el modelo de memoria externa: hay un algoritmo propuesto debido a Dementiev et al. que se afirma que es solo de dos a cinco veces más lento que un algoritmo que solo hace uso de la memoria interna [11]
Referencias
- ^ Sanders; Dietzfelbinger; Martín; Mehlhorn; Kurt; Peter (10 de junio de 2014). Algorithmen und Datenstrukturen Die Grundwerkzeuge . Springer Vieweg. ISBN 978-3-642-05472-3.
- ^ Brodal, Gerth Stølting; Träff, Jesper Larsson; Zaroliagis, Christos D. (1998), "A Parallel Priority Queue with Constant Time Operations", Journal of Parallel and Distributed Computing , 49 (1): 4–21, CiteSeerX 10.1.1.48.3272 , doi : 10.1006 / jpdc.1998.1425
- ^ Osipov, Vitaly; Sanders, Peter; Singler, Johannes (2009), "El algoritmo del árbol de expansión mínimo filter-kruskal", Actas del Undécimo Taller de Ingeniería de Algoritmos y Experimentos (ALENEX). Sociedad de Matemáticas Industriales y Aplicadas : 52–61, CiteSeerX 10.1.1.218.2574
- ^ Sanders, Peter. "Script de ingeniería de algoritmos" (PDF) . Página de inicio del KIT de ingeniería de algoritmos . Consultado el 25 de febrero de 2019 .
- ^ Sanders, Peter. "Script de algoritmos paralelos" (PDF) . Página de inicio del KIT de algoritmos paralelos . Consultado el 25 de febrero de 2019 .
- ^ Zadeh, Reza. "Optimización y algoritmos distribuidos" (PDF) . Optimización y algoritmos distribuidos Página de inicio de la Universidad de Stanford . Consultado el 25 de febrero de 2019 .
- ^ Chun, Sun; Condon, Anne (1996). "Implementación paralela del algoritmo de árbol de expansión mínimo de Bouvka". Actas de la Conferencia Internacional sobre Procesamiento Paralelo : 302–308. doi : 10.1109 / IPPS.1996.508073 . ISBN 0-8186-7255-2.
- ^ Chong, Ka Wong; Han, Yijie; Lam, Tak Wah (2001), "Hilos concurrentes y algoritmo de árboles de expansión mínimos paralelos óptimos", Journal of the Association for Computing Machinery , 48 (2): 297–323, CiteSeerX 10.1.1.32.1554 , doi : 10.1145 / 375827.375847 , Señor 1868718
- ^ Pettie, Seth; Ramachandran, Vijaya (2002), "Un algoritmo paralelo óptimo de trabajo en tiempo aleatorio para encontrar un bosque de expansión mínimo" (PDF) , SIAM Journal on Computing , 31 (6): 1879–1895, doi : 10.1137 / S0097539700371065 , MR 1954882
- ^ Bader, David A .; Cong, Guojing (2006), "Algoritmos rápidos de memoria compartida para calcular el bosque de expansión mínimo de gráficos dispersos", Journal of Parallel and Distributed Computing , 66 (11): 1366-1378, doi : 10.1016 / j.jpdc.2006.06. 001
- ^ Dementiev, Roman; Sanders, Peter; Schultes, Dominik; Sibeyn, Jop F. (2004), "Ingeniería de un algoritmo de árbol de expansión mínimo de memoria externa", Proc. IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004) (PDF) , págs. 195–208.