Algoritmo de Prim

Método para encontrar árboles de expansión mínimos

Una demostración del algoritmo de Prim basado en la distancia euclidiana

En informática , el algoritmo de Prim es un algoritmo voraz que encuentra un árbol de expansión mínimo para un grafo no dirigido ponderado . Esto significa que encuentra un subconjunto de las aristas que forman un árbol que incluye cada vértice , donde el peso total de todas las aristas del árbol se minimiza. El algoritmo funciona construyendo este árbol un vértice a la vez, a partir de un vértice inicial arbitrario, y en cada paso agregando la conexión más barata posible desde el árbol a otro vértice.

El algoritmo fue desarrollado en 1930 por el matemático checo Vojtěch Jarník ^[1] y posteriormente redescubierto y republicado por los científicos informáticos Robert C. Prim en 1957 ^[2] y Edsger W. Dijkstra en 1959. ^[3] Por lo tanto, a veces también se le llama algoritmo de Jarník , ^[4] algoritmo de Prim-Jarník , ^[5] algoritmo de Prim-Dijkstra ^[6] o algoritmo DJP . ^[7]

Otros algoritmos conocidos para este problema incluyen el algoritmo de Kruskal y el algoritmo de Borůvka . ^[8] Estos algoritmos encuentran el bosque de expansión mínimo en un gráfico posiblemente desconectado; en contraste, la forma más básica del algoritmo de Prim solo encuentra árboles de expansión mínimos en gráficos conectados. Sin embargo, al ejecutar el algoritmo de Prim por separado para cada componente conectado del gráfico, también se puede utilizar para encontrar el bosque de expansión mínimo. ^[9] En términos de su complejidad temporal asintótica , estos tres algoritmos son igualmente rápidos para gráficos dispersos , pero más lentos que otros algoritmos más sofisticados. ^{[7] [6]} Sin embargo, para gráficos que son suficientemente densos, el algoritmo de Prim se puede ejecutar en tiempo lineal , cumpliendo o mejorando los límites de tiempo para otros algoritmos. ^[10]

El algoritmo de Prim comienza en el vértice A. En el tercer paso, las aristas BD y AB tienen peso 2, por lo que se elige BD de manera arbitraria. Después de ese paso, AB ya no es candidato para agregarse al árbol porque vincula dos nodos que ya están en el árbol.

Descripción

El algoritmo puede describirse informalmente como la realización de los siguientes pasos:

1. Inicializar un árbol con un único vértice, elegido arbitrariamente del gráfico.
2. Haga crecer el árbol por un borde: de los bordes que conectan el árbol con vértices que aún no están en el árbol, encuentre el borde de peso mínimo y transfiéralo al árbol.
3. Repita el paso 2 (hasta que todos los vértices estén en el árbol).

Con más detalle se puede implementar siguiendo el pseudocódigo a continuación.

1. Asocie a cada vértice v del grafo un número C [ v ] (el costo más bajo de una conexión a v ) y una arista E [ v ] (la arista que proporciona esa conexión más barata). Para inicializar estos valores, establezca todos los valores de C [ v ] en +∞ (o en cualquier número mayor que el peso máximo de la arista) y establezca cada E [ v ] en un valor de bandera especial que indica que no hay ninguna arista que conecte v con vértices anteriores.
2. Inicializar un bosque vacío F y un conjunto Q de vértices que aún no se han incluido en F (inicialmente, todos los vértices).
3. Repita los siguientes pasos hasta que Q esté vacío:
   1. Encuentra y elimina un vértice v de Q que tenga el mínimo valor posible de C [ v ]
   2. Añadir v a F
   3. Realizar un bucle sobre las aristas vw que conectan v con otros vértices w . Para cada una de esas aristas, si w todavía pertenece a Q y vw tiene un peso menor que C [ w ], realizar los siguientes pasos:
      1. Establezca C [ w ] en el costo del borde vw
      2. Establezca E [ w ] para apuntar al borde vw .
4. Devuelve F , que incluye específicamente los bordes correspondientes en E

Como se describió anteriormente, el vértice inicial para el algoritmo se elegirá arbitrariamente, porque la primera iteración del bucle principal del algoritmo tendrá un conjunto de vértices en Q que tienen todos pesos iguales, y el algoritmo iniciará automáticamente un nuevo árbol en F cuando complete un árbol de expansión de cada componente conectado del gráfico de entrada. El algoritmo se puede modificar para comenzar con cualquier vértice particular s estableciendo C [ s ] como un número menor que los otros valores de C (por ejemplo, cero), y se puede modificar para encontrar solo un único árbol de expansión en lugar de un bosque de expansión completo (que coincide más estrechamente con la descripción informal) deteniéndose siempre que encuentre otro vértice marcado como que no tiene una arista asociada.

Las distintas variantes del algoritmo difieren entre sí en la forma en que se implementa el conjunto Q : como una simple lista enlazada o matriz de vértices, o como una estructura de datos de cola de prioridad más complicada. Esta elección conduce a diferencias en la complejidad temporal del algoritmo. En general, una cola de prioridad será más rápida para encontrar el vértice v con un costo mínimo, pero implicará actualizaciones más costosas cuando cambie el valor de C [ w ].

Complejidad temporal

El algoritmo de Prim tiene muchas aplicaciones, como por ejemplo en la generación de este laberinto, que aplica el algoritmo de Prim a un gráfico de cuadrícula ponderado aleatoriamente .

La complejidad temporal del algoritmo de Prim depende de las estructuras de datos utilizadas para el gráfico y para ordenar los bordes por peso, lo que se puede hacer utilizando una cola de prioridad . La siguiente tabla muestra las opciones típicas:

Una implementación simple de Prim, que utiliza una matriz de adyacencia o una representación gráfica de lista de adyacencia y busca linealmente una matriz de pesos para encontrar la arista de peso mínimo que se debe agregar, requiere un tiempo de ejecución de O (|V| ² ). Sin embargo, este tiempo de ejecución se puede mejorar en gran medida utilizando montículos para implementar la búsqueda de aristas de peso mínimo en el bucle interno del algoritmo.

Una primera versión mejorada utiliza un montón para almacenar todos los bordes del gráfico de entrada, ordenados por su peso. Esto lleva a un tiempo de ejecución de O(|E| log |E|) en el peor de los casos. Pero almacenar vértices en lugar de bordes puede mejorarlo aún más. El montón debe ordenar los vértices por el peso de borde más pequeño que los conecta a cualquier vértice en el árbol de expansión mínimo (MST) parcialmente construido (o infinito si no existe tal borde). Cada vez que se elige un vértice v y se agrega al MST, se realiza una operación de disminución de clave en todos los vértices w fuera del MST parcial de modo que v esté conectado a w , fijando la clave en el mínimo de su valor anterior y el costo de borde de ( v , w ).

Usando una estructura de datos de montón binario simple , ahora se puede demostrar que el algoritmo de Prim se ejecuta en tiempo O (|E| log |V|) donde |E| es el número de aristas y |V| es el número de vértices. Usando un montón de Fibonacci más sofisticado , esto se puede reducir a O (|E| + |V| log |V|), que es asintóticamente más rápido cuando el gráfico es lo suficientemente denso como para que |E| sea ω (|V|), y tiempo lineal cuando |E| es al menos |V| log |V|. Para gráficos de densidad aún mayor (que tengan al menos |V| ^c aristas para algún c  > 1), el algoritmo de Prim se puede hacer que se ejecute en tiempo lineal aún más simplemente, usando un montón d -ario en lugar de un montón de Fibonacci. ^{[10] [11]}

Demostración de la prueba. En este caso, el grafo Y ₁ = Y − f + e ya es igual a Y . En general, puede ser necesario repetir el proceso.

Prueba de corrección

Sea P un grafo ponderado y conexo . En cada iteración del algoritmo de Prim, se debe encontrar una arista que conecte un vértice en un subgrafo con un vértice fuera del subgrafo. Como P es conexo, siempre habrá un camino hacia cada vértice. La salida Y del algoritmo de Prim es un árbol , porque la arista y el vértice agregados al árbol Y están conexos. Sea Y ₁ un árbol de expansión mínimo del grafo P. Si Y ₁ = Y entonces Y es un árbol de expansión mínimo. De lo contrario, sea e la primera arista agregada durante la construcción del árbol Y que no está en el árbol Y ₁ , y sea V el conjunto de vértices conectados por las aristas agregadas antes de la arista e . Entonces un punto final de la arista e está en el conjunto V y el otro no. Como el árbol Y ₁ es un árbol de expansión del grafo P , hay un camino en el árbol Y ₁ que une los dos puntos finales. A medida que uno viaja a lo largo del camino, debe encontrar una arista f que une un vértice en el conjunto V con uno que no está en el conjunto V . Ahora, en la iteración en la que se agregó la arista e al árbol Y , también se podría haber agregado la arista f y se agregaría en lugar de la arista e si su peso fuera menor que e , y dado que no se agregó la arista f , concluimos que

${\displaystyle w(f)\geq w(e).}$

Sea el árbol Y ₂ el grafo obtenido al eliminar la arista f y agregar la arista e al árbol Y ₁ . Es fácil demostrar que el árbol Y ₂ es conexo, tiene el mismo número de aristas que el árbol Y ₁ , y los pesos totales de sus aristas no son mayores que los del árbol Y ₁ , por lo tanto, también es un árbol de expansión mínimo del grafo P y contiene la arista e y todas las aristas agregadas antes de él durante la construcción del conjunto V . Repita los pasos anteriores y eventualmente obtendremos un árbol de expansión mínimo del grafo P que es idéntico al árbol Y . Esto demuestra que Y es un árbol de expansión mínimo. El árbol de expansión mínimo permite que el primer subconjunto de la subregión se expanda en un subconjunto más grande X , que asumimos que es el mínimo.

Algoritmo paralelo

La matriz de adyacencia distribuida entre múltiples procesadores para el algoritmo de Prim en paralelo. En cada iteración del algoritmo, cada procesador actualiza su parte de C inspeccionando la fila del vértice recién insertado en su conjunto de columnas en la matriz de adyacencia. Luego se recopilan los resultados y se selecciona globalmente el siguiente vértice que se incluirá en la MST.

El bucle principal del algoritmo de Prim es inherentemente secuencial y, por lo tanto, no paralelizable . Sin embargo, el bucle interno, que determina el siguiente borde de peso mínimo que no forma un ciclo, se puede paralelizar dividiendo los vértices y los bordes entre los procesadores disponibles. ^[12] El siguiente pseudocódigo demuestra esto.

1. Asigna a cada procesador un conjunto de vértices consecutivos de longitud . ${\displaystyle P_{i}}$ ${\displaystyle V_{i}}$ ${\displaystyle {\tfrac {|V|}{|P|}}}$
2. Cree C, E, F y Q como en el algoritmo secuencial y divida C, E, así como el gráfico entre todos los procesadores de modo que cada procesador mantenga las aristas entrantes en su conjunto de vértices. Sea , la parte de C , E almacenada en el procesador . ${\displaystyle C_{i}}$ ${\displaystyle E_{i}}$ ${\displaystyle P_{i}}$
3. Repita los siguientes pasos hasta que Q esté vacío:
   1. En cada procesador: encuentre el vértice que tenga el valor mínimo en [ ] (solución local). ${\displaystyle v_{i}}$ ${\displaystyle C_{i}}$ ${\displaystyle v_{i}}$
   2. Minimiza las soluciones locales para encontrar el vértice v que tenga el mínimo valor posible de C [ v ] (solución global).
   3. Transmitir el nodo seleccionado a todos los procesadores.
   4. Agregue v a F y, si E [ v ] no es el valor de bandera especial, agregue también E [ v ] a F.
   5. En cada procesador: actualizar y como en el algoritmo secuencial. ${\displaystyle C_{i}}$ ${\displaystyle E_{i}}$
4. Devolver F

Este algoritmo se puede implementar generalmente en máquinas distribuidas ^[12] así como en máquinas de memoria compartida. ^[13] El tiempo de ejecución es , asumiendo que las operaciones de reducción y difusión se pueden realizar en . ^[12] También se ha explorado una variante del algoritmo de Prim para máquinas de memoria compartida, en la que el algoritmo secuencial de Prim se ejecuta en paralelo, comenzando desde diferentes vértices. ^[14] Sin embargo, debe notarse que existen algoritmos más sofisticados para resolver el problema del árbol de expansión mínimo distribuido de una manera más eficiente. ${\displaystyle O({\tfrac {|V|^{2}}{|P|}})+O(|V|\log |P|)}$ ${\displaystyle O(\log |P|)}$

Véase también

• Algoritmo de Dijkstra , un algoritmo muy similar para el problema del camino más corto
• Los Greedoids ofrecen una forma general de entender la corrección del algoritmo de Prim.

Referencias

1. Jarník, V. (1930), "O jistém problému minimálním" [Sobre cierto problema mínimo], Práce Moravské Přírodovědecké Společnosti (en checo), 6 (4): 57–63, hdl :10338.dmlcz/500726.
2. Prim, RC (noviembre de 1957), "Redes de conexión más cortas y algunas generalizaciones", Bell System Technical Journal , 36 (6): 1389–1401, Bibcode :1957BSTJ...36.1389P, doi :10.1002/j.1538-7305.1957.tb01515.x.
3. Dijkstra, EW (diciembre de 1959), "Una nota sobre dos problemas relacionados con gráficos" (PDF) , Numerische Mathematik , 1 (1): 269–271, CiteSeerX 10.1.1.165.7577 , doi :10.1007/BF01386390, S2CID  123284777 .
4. Sedgewick, Robert ; Wayne, Kevin Daniel (2011), Algoritmos (4.ª ed.), Addison-Wesley, pág. 628, ISBN 978-0-321-57351-3.
5. Rosen, Kenneth (2011), Matemáticas discretas y sus aplicaciones (7.ª ed.), McGraw-Hill Science, pág. 798.
6. Cheriton, David ; Tarjan, Robert Endre (1976), "Encontrar árboles de expansión mínimos", SIAM Journal on Computing , 5 (4): 724–742, doi :10.1137/0205051, MR  0446458.
7. Pettie, Seth; Ramachandran, Vijaya (enero de 2002), "Un algoritmo óptimo de árbol de expansión mínimo" (PDF) , Journal of the ACM , 49 (1): 16–34, CiteSeerX 10.1.1.110.7670 , doi :10.1145/505241.505243, MR  2148431, S2CID  5362916 .
8. Tarjan, Robert Endre (1983), "Capítulo 6. Árboles de expansión mínimos. 6.2. Tres algoritmos clásicos", Estructuras de datos y algoritmos de red , Serie de conferencias regionales CBMS-NSF sobre matemáticas aplicadas, vol. 44, Sociedad de matemáticas industriales y aplicadas , págs. 72–77.
9. Kepner, Jeremy; Gilbert, John (2011), Algoritmos gráficos en el lenguaje del álgebra lineal, Software, entornos y herramientas, vol. 22, Society for Industrial and Applied Mathematics , pág. 55, ISBN 9780898719901.
10. Tarjan (1983), pág. 77.
11. Johnson, Donald B. (diciembre de 1975), "Colas de prioridad con árboles de expansión mínimos de actualización y búsqueda", Information Processing Letters , 4 (3): 53–57, doi :10.1016/0020-0190(75)90001-0.
12. Grama, Ananth; Gupta, Anshul; Karypis, George; Kumar, Vipin (2003), Introducción a la computación paralela , Addison-Wesley, págs. 444–446, ISBN 978-0201648652
13. Quinn, Michael J.; Deo, Narsingh (1984), "Algoritmos de gráficos paralelos", ACM Computing Surveys , 16 (3): 319–348, doi : 10.1145/2514.2515 , S2CID  6833839
14. Setia, Rohit (2009), "Un nuevo algoritmo paralelo para el problema del árbol de expansión mínimo" (PDF) , Proc. Conferencia internacional sobre computación de alto rendimiento (HiPC)

Enlaces externos

• Progreso del algoritmo de Prim en puntos distribuidos aleatoriamente
• Medios relacionados con el algoritmo de Prim en Wikimedia Commons