Algoritmos paralelos para árboles de expansión mínima

En teoría de grafos, un árbol de expansión mínima (MST)${\displaystyle T}$de un gráfico${\displaystyle G=(V,E)}$con${\displaystyle |V|=n}$y${\displaystyle |E|=m}$es un subgrafo de árbol de${\displaystyle G}$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 desde un único almacén podría usar un MST que se origine en el almacén para calcular las rutas más cortas a cada tienda. En este caso, las tiendas y el almacén se representan como vértices y las conexiones viales entre ellos, como aristas. Cada arista está etiquetada con la longitud de la conexión vial correspondiente.

Si${\displaystyle G}$En el caso sin ponderación de aristas, cada árbol de expansión posee el mismo número de aristas y, por lo tanto, el mismo peso. En el caso con ponderación de aristas , el árbol de expansión, cuya suma de los pesos de las aristas es la más baja entre todos los árboles de expansión de${\displaystyle G}$, se denomina árbol de expansión mínima (MST). No es necesariamente único. De manera más general, los grafos que no están necesariamente conectados tienen bosques de expansión mínima , 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 utilizando diferentes propiedades de los MST. Todos operan de manera similar: un subconjunto de${\displaystyle E}$se desarrolla iterativamente hasta que se descubre un MST válido. Sin embargo, dado que los problemas prácticos suelen ser bastante grandes (las redes de carreteras a veces tienen miles de millones de aristas), el rendimiento es un factor clave. Una opción para mejorarlo es paralelizando los algoritmos MST conocidos . ^{[ 1 ]}

Este algoritmo utiliza la propiedad de corte de los MST. A continuación se proporciona una implementación sencilla en pseudocódigo de alto nivel :

${\displaystyle T\gets \emptyset }$${\displaystyle S\gets \{s\}}$dónde${\displaystyle s}$es un vértice aleatorio en${\displaystyle V}$repetir${\displaystyle |V|-1}$veces encontrar el borde más ligero${\displaystyle (u,v)}$calle${\displaystyle u\in S}$pero${\displaystyle v\in (V\setminus S)}$${\displaystyle S\gets S\cup \{v\}}$${\displaystyle T\gets T\cup \{(u,v)\}}$devolver T

Cada arista se observa exactamente dos veces, es decir, al examinar cada uno de sus extremos. Cada vértice se examina exactamente una vez para un total de${\displaystyle O(n+m)}$operaciones aparte de la selección del borde más ligero en cada iteración del bucle. Esta selección a menudo se realiza utilizando una cola de prioridad (PQ). Para cada borde como máximo una operación decreaseKey ( amortizada en${\displaystyle O(1)}$) se realiza y cada iteración del bucle realiza una operación deleteMin (${\displaystyle O(\log n)}$). Por lo tanto, utilizando montículos de Fibonacci, el tiempo total de ejecución del algoritmo de Prim es asintóticamente en${\displaystyle O(m+n\log n)}$.

Es importante señalar que el bucle es inherentemente secuencial y no se puede paralelizar correctamente. Este es el caso, ya que el borde más ligero con un extremo en${\displaystyle S}$y en${\displaystyle V\setminus S}$podría cambiar con la adición de bordes a${\displaystyle T}$Por lo tanto, no se pueden realizar dos selecciones del borde más claro al mismo tiempo. Sin embargo, existen algunos intentos de paralelización .

Una posible idea es utilizar${\displaystyle O(n)}$procesadores para admitir el acceso PQ en${\displaystyle O(1)}$en una máquina EREW-PRAM , ^{[ 2 ]} reduciendo así el tiempo total de ejecución a${\displaystyle O(n+m)}$.

El algoritmo MST de Kruskal utiliza la propiedad de ciclo de los MST. A continuación se proporciona una representación en pseudocódigo de alto nivel.

${\displaystyle T\gets }$bosque con cada vértice en su propio subárbol para cada${\displaystyle (u,v)\in E}$en orden ascendente de peso si${\displaystyle u}$y${\displaystyle v}$en diferentes subárboles de${\displaystyle T}$${\displaystyle T\gets T\cup \{(u,v)\}}$devolver T

Los subárboles de${\displaystyle T}$se almacenan en estructuras de datos de unión-búsqueda , por lo que es posible comprobar si dos vértices están o no en el mismo subárbol en amortizado${\displaystyle O(\alpha (m,n))}$dónde${\displaystyle \alpha (m,n)}$es la función inversa de Ackermann . Por lo tanto, el tiempo total de ejecución del algoritmo es de${\displaystyle O(sort(n)+\alpha (n))}$. Aquí${\displaystyle \alpha (n)}$denota la función inversa de Ackermann de valor único, para la cual cualquier entrada realista produce un número entero menor que cinco.

filtroKruskal(${\displaystyle G}$): si${\displaystyle m<}$KruskalThreshold: devolver kruskal(${\displaystyle G}$) pivote = elegirAleatorio(${\displaystyle E}$) ${\displaystyle (E_{\leq }}$,${\displaystyle E_{>})\gets }$dividir(${\displaystyle E}$, pivote) ${\displaystyle A\gets }$filtroKruskal(${\displaystyle E_{\leq }}$) ${\displaystyle E_{>}\gets }$filtrar(${\displaystyle E_{>}}$) ${\displaystyle A\gets A}$${\displaystyle \cup }$filtroKruskal(${\displaystyle E_{>}}$) devolver${\displaystyle A}$ dividir(${\displaystyle E}$, pivote): ${\displaystyle E_{\leq }\gets \emptyset }$${\displaystyle E_{>}\gets \emptyset }$para cada${\displaystyle (u,v)\in E}$: si peso(${\displaystyle u,v}$)${\displaystyle \leq }$pivote: ${\displaystyle E_{\leq }\gets E_{\leq }\cup {(u,v)}}$demás${\displaystyle E_{>}\gets E_{>}\cup {(u,v)}}$devolver (${\displaystyle E_{\leq }}$,${\displaystyle E_{>}}$) filtrar(${\displaystyle E}$): ${\displaystyle E_{filtered}\gets \emptyset }$para cada${\displaystyle (u,v)\in E}$: si find-set(u)${\displaystyle \neq }$encontrar-conjunto(v): ${\displaystyle E_{filtered}\gets E_{filtered}\cup {(u,v)}}$devolver${\displaystyle E_{filtrado}}$

La idea principal detrás del algoritmo de Borůvka es la contracción de aristas . Una arista${\displaystyle \{u,v\}}$se contrae eliminando primero${\displaystyle v}$desde el gráfico y luego redirigiendo cada arista${\displaystyle \{w,v\}\in E}$a${\displaystyle \{w,u\}}$Estas nuevas aristas conservan sus pesos originales. Si el objetivo no es solo determinar el peso de un MST, sino también qué aristas lo componen, debe tenerse en cuenta entre qué pares de vértices se contrajo una arista. Representación en pseudocódigo de alto nivel:

${\displaystyle T\gets \emptyset }$mientras${\displaystyle |V|>1}$${\displaystyle S\gets \emptyset }$para${\displaystyle v\in V}$${\displaystyle S\gets S}$${\displaystyle \cup }$más ligero${\displaystyle \{u,v\}\in E}$para${\displaystyle \{u,v\}\in S}$ contrato${\displaystyle \{u,v\}}$${\displaystyle T\gets T\cup S}$devolver T

Es posible que las contracciones den lugar a múltiples aristas entre un par de vértices. La forma intuitiva de elegir la más ligera de ellas no es posible en${\displaystyle O(m)}$Sin embargo, si todas las contracciones que comparten un vértice se realizan en paralelo, esto es factible. La recursión se detiene cuando solo queda un único vértice, lo que significa que el algoritmo necesita como máximo${\displaystyle \log n}$iteraciones, lo que lleva a un tiempo de ejecución total en${\displaystyle O(m\log n)}$.

mientras${\displaystyle |V|>1}$ encontrar los bordes de incidencia más ligeros //${\displaystyle O({\frac {m}{p}}+\log n+\log p)}$ asignar el subgrafo correspondiente a cada vértice //${\displaystyle O({\frac {n}{p}}+\log n)}$ contraer cada subgrafo //${\displaystyle O({\frac {m}{p}}+\log n)}$

${\displaystyle v\gets }$encontrar(${\displaystyle {\frac {im}{p}}}$,${\displaystyle \Gamma }$) para${\displaystyle e\gets {\frac {im}{p}};e<{\frac {(i+1)m}{p}}-1;e++}$si${\displaystyle \Gamma [v+1]=e}$${\displaystyle v++}$si${\displaystyle c[e]<c[pred[v]]}$${\displaystyle pred[v]\gets e}$

paralelo para todos${\displaystyle v\in V}$${\displaystyle w\gets pred[v]}$si${\displaystyle pred[w]=v\land v<w}$${\displaystyle pred[v]\gets v}$

mientras${\displaystyle \exists v\in V:pred[v]\neq pred[pred[v]]}$para todos${\displaystyle v\in V}$${\displaystyle pred[v]\gets pred[pred[v]]}$

${\displaystyle k\gets }$número de subgrafos ${\displaystyle V'\gets \{0,\dots ,k-1\}}$ encontrar una función biyectiva${\displaystyle f:}$raíz estrellada${\displaystyle \rightarrow \{0,\dots ,k-1\}}$${\displaystyle E'\gets \{(f(pred[v]),f(pred[w]),c,e_{old}):(v,w)\in E\land pred[v]\neq pred[w]\}}$

Existen otros múltiples algoritmos paralelos que abordan el problema de encontrar un MST. Con un número lineal de procesadores es posible lograr esto en${\displaystyle O(\log n)}$. ^{[ 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: existe un algoritmo propuesto por Dementiev et al. que afirma ser solo de dos a cinco veces más lento que un algoritmo que solo utiliza la memoria interna ^{[ 11 ].}