la implementación de las discusiones del algoritmo de Kruskal utilización
-
13-09-2019 - |
Pregunta
estoy poniendo en práctica el algoritmo de Kruskal y me gustaría utilizar hilos. Sin embargo no estoy seguro de que sé lo suficiente sobre el algoritmo para hacer esto.
Lo que me imagino es que había diferentes partes del gráfico se resolverían para y se conectan al final. ¿Puede alguien me punto en la dirección correcta? Gracias.
Solución
La investigación se ha centrado en la solución de la problema del árbol de expansión mínimo en una manera altamente paralelizado. Con un número lineal de procesadores es posible resolver el problema de O (log n) tiempo. Un documento de 2003 "rápido Memoria compartida-Algoritmos para la Computación el Bosque de expansión mínimo de escasa Los gráficos" de David A. Bader y Guojing Cong demuestra una pragmática algoritmo que puede calcular MSTs 5 8 veces más rápido en los procesadores de una optimizado algoritmo secuencial. [9] Típicamente, algoritmos paralelos son basado en el algoritmo de Prim-de Boruvka y especialmente el algoritmo de Kruskal hacer No escalar, así que adicional procesadores.
Por lo tanto, es posible mirar en el algoritmo mencionado en dicho papel, pero Kruskal probablemente no se beneficiará de múltiples hilos.
Otros consejos
algoritmo de Kruskal para el MST es difícil poner en paralelo porque considera bordes en un orden estrictamente especificado. Usted debe echar un vistazo a algoritmo de Boruvka que es más fácil para paralelizar como se puede trabajar en cada subárbol de un MST parcial independiente.