algoritmo de primi

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

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

En informática , el algoritmo de Prim es un algoritmo codicioso que encuentra un árbol de expansión mínimo para un gráfico no dirigido ponderado . Esto significa que encuentra un subconjunto de las aristas que forma un árbol que incluye cada vértice , donde se minimiza el peso total de todas las aristas del árbol. El algoritmo opera construyendo este árbol un vértice a la vez, desde un vértice inicial arbitrario, agregando en cada paso la conexión más barata posible del á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 reeditado 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 el algoritmo DJP . ^[7]

Otros algoritmos bien 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ínima en un gráfico posiblemente desconectado; por el contrario, la forma más básica del algoritmo de Prim sólo 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ínima. ^[9] En términos de su complejidad de tiempo 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, se puede hacer que el algoritmo de Prim se ejecute en tiempo lineal , cumpliendo o mejorando los límites de tiempo de otros algoritmos. ^[10]

El algoritmo de Prim comienza en el vértice A. En el tercer paso, los bordes BD y AB tienen peso 2, por lo que BD se elige arbitrariamente. 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 realizando los siguientes pasos:

1. Inicialice un árbol con un solo vértice, elegido arbitrariamente del gráfico.
2. Haga crecer el árbol por un borde: de los bordes que conectan el árbol con los 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 siguiente.

1. Asocie con cada vértice v del gráfico un número C [ v ] (el costo más barato 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 borde) y establezca cada E [ v ] en un valor de indicador especial que indique que no hay ningún borde que conecte v con el anterior. vértices.
2. Inicialice 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. Encuentre y elimine un vértice v de Q que tenga el valor mínimo posible de C [ v ]
   2. Sumar v a F
   3. Haga un bucle sobre los bordes vw que conectan v con otros vértices w . Para cada uno de esos bordes, si w todavía pertenece a Q y vw tiene un peso menor que C [ w ], realice los siguientes pasos:
      1. Establezca C [ w ] al costo de Edge VW
      2. Establezca E [ w ] para que apunte al borde vw .
4. Devuelve F , que incluye específicamente los bordes correspondientes en E

Como se describió anteriormente, el vértice inicial del algoritmo se elegirá arbitrariamente, porque la primera iteración del bucle principal del algoritmo tendrá un conjunto de vértices en Q todos con pesos iguales, y el algoritmo iniciará automáticamente un nuevo árbol en F cuando completa 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 s en particular 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 completo (que coincide más estrechamente con la descripción informal) deteniéndose cada vez que encuentra otro vértice marcado como sin borde asociado.

Las diferentes variaciones del algoritmo se diferencian entre sí en cómo se implementa el conjunto Q : como una lista enlazada simple o una 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 del tiempo

El algoritmo de Prim tiene muchas aplicaciones, como 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 mediante una cola de prioridad . La siguiente tabla muestra las opciones típicas:

Una implementación simple de Prim, usando una matriz de adyacencia o una representación gráfica de lista de adyacencia y buscando linealmente una matriz de pesos para encontrar el borde de peso mínimo para agregar, requiere tiempo de ejecución O (|V| ² ). Sin embargo, este tiempo de ejecución se puede mejorar enormemente mediante el uso de montones para implementar la búsqueda de bordes 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 conduce a un tiempo de ejecución en el peor de los casos O(|E| log |E|). Pero almacenar vértices en lugar de aristas 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ínima (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 clave de disminución en todos los vértices w fuera del MST parcial de manera que v esté conectado a w , estableciendo la clave al mínimo de su valor anterior y el costo del borde. de ( v , w ).

Utilizando una estructura de datos de montón binario simple , ahora se puede demostrar que el algoritmo de Prim se ejecuta en el 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| es ω (|V|), y el tiempo lineal cuando |E| es al menos |V| registro |V|. Para gráficos de densidad aún mayor (que tienen al menos |V| ^c aristas para algunos c  > 1), se puede hacer que el algoritmo de Prim se ejecute en tiempo lineal de manera aún más simple, usando un montón d -ario en lugar de un montón de Fibonacci. ^{[10] [11]}

Demostración de prueba. En este caso, la gráfica Y ₁ = Y − f + e ya es igual a Y . En general, es posible que sea necesario repetir el proceso.

Prueba de corrección

Sea P un gráfico 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 a cada vértice. La salida Y del algoritmo de Prim es un árbol , porque el borde y el vértice agregados al árbol Y están conectados. Sea Y ₁ un árbol de expansión mínimo del gráfico 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 V sea el conjunto de vértices conectados por las aristas agregadas antes de la arista e . Entonces un punto final del borde e está en el conjunto V y el otro no. Dado que el árbol Y ₁ es un árbol de expansión del gráfico P , hay una ruta 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 cuando se agregó el borde e al árbol Y , también se podría haber agregado el borde f y se agregaría en lugar del borde e si su peso fuera menor que e , y como el borde f no se agregó, concluimos que

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

Sea el árbol Y ₂ el gráfico obtenido eliminando el borde f y agregando el borde e al árbol Y ₁ . Es fácil demostrar que el árbol Y ₂ está conectado, 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 gráfico. P y contiene el borde e y todos los bordes agregados antes durante la construcción del conjunto V. Repita los pasos anteriores y eventualmente obtendremos un árbol de expansión mínimo del gráfico P que es idéntico al árbol Y. Esto muestra 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 a un subconjunto X más grande , que suponemos 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 a incluir en el MST.

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

1. Asigne 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 los bordes entrantes en su conjunto de vértices. Denotemos las partes de C , E almacenadas 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 tiene el valor mínimo en [ ] (solución local). ${\displaystyle v_{i}}$ ${\displaystyle C_{i}}$ ${\displaystyle v_{i}}$
   2. Reduzca al mínimo las soluciones locales para encontrar el vértice v que tenga el valor mínimo posible de C [ v ] (solución global).
   3. Transmita el nodo seleccionado a cada procesador.
   4. Agregue v a F y, si E [ v ] no es el valor del indicador 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. Volver F

Este algoritmo generalmente se puede implementar en máquinas distribuidas ^[12] así como en máquinas de memoria compartida. ^[13] El tiempo de ejecución es , suponiendo que las operaciones de reducción y transmisió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, cabe señalar 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|)}$

Ver también

• Algoritmo de Dijkstra , un algoritmo muy similar para el problema del camino más corto
• Los codiciosos ofrecen una forma general de comprender 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. 798.
6. Cheriton, David ; Tarjan, Robert Endre (1976), "Encontrar árboles de expansión mínima", SIAM Journal on Computing , 5 (4): 724–742, doi :10.1137/0205051, SEÑOR  0446458.
7. Pettie, Seth; Ramachandran, Vijaya (enero de 2002), "Un algoritmo de árbol de expansión mínimo óptimo" (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ínima. 6.2. Tres algoritmos clásicos", Estructuras de datos y algoritmos de red , Serie de conferencias regionales CBMS-NSF en 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 de álgebra lineal, software, entornos y herramientas, vol. 22, Sociedad de Matemáticas Industriales y Aplicadas , p. 55, ISBN 9780898719901.
10. Tarjan (1983), pág. 77.
11. Johnson, Donald B. (diciembre de 1975), "Colas prioritarias con actualización y búsqueda de árboles de expansión mínimos", Cartas de procesamiento de información , 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 , 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ínima" (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