Algoritmo de Prim - Prim's algorithm

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

En informática , el algoritmo de Prim (también conocido como algoritmo de Jarník) es un algoritmo codicioso que encuentra un árbol de expansión mínimo para un gráfico ponderado no dirigido . Esto significa que encuentra un subconjunto de los bordes que forma un árbol que incluye todos los vértices , donde se minimiza el peso total de todos los bordes del árbol. El algoritmo opera construyendo este árbol un vértice a la vez, desde un vértice inicial arbitrario, en cada paso agregando la conexión más barata posible del árbol a otro vértice.

El algoritmo fue desarrollado en 1930 por Checa matemático Vojtěch Jarník y más tarde redescubierto y publicado de nuevo por los informáticos Robert C. Prim en 1957 y Edsger Dijkstra en 1959. Por lo tanto, también a veces se llama el algoritmo de Jarnik , algoritmo de Prim-Jarnik , Prim –Algoritmo Dijkstra o el algoritmo DJP .

Otros algoritmos bien conocidos para este problema incluyen el algoritmo de Kruskal y el algoritmo de Borůvka . Estos algoritmos encuentran el bosque de expansión mínimo en un gráfico posiblemente desconectado; por el contrario, 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 usar para encontrar el bosque de expansión mínimo. 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. Sin embargo, para gráficos que son lo suficientemente densos, se puede hacer que el algoritmo de Prim se ejecute en tiempo lineal , cumpliendo o mejorando los límites de tiempo para otros algoritmos.

El algoritmo de Prim comienza en el vértice A. En el tercer paso, las aristas BD y AB tienen un peso 2, por lo que BD se elige arbitrariamente. Después de ese paso, AB ya no es candidato para ser agregado 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:

Inicialice un árbol con un solo vértice, elegido arbitrariamente del gráfico.
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, busque el borde de peso mínimo y transfiéralo al árbol.
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.

Asocie con cada vértice v del gráfico un número C [ v ] (el costo más barato de una conexión av ) y un borde E [ v ] (el borde 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 del borde) y establezca cada E [ v ] en un valor de marca especial que indica que no hay ningún borde que conecte v con el anterior. vértices.
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).
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. Agregue v a F y, si E [ v ] no es el valor especial de la bandera, agregue también E [ v ] a F
3. 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 ] en el costo del borde vw
  2. Configure E [ w ] para que apunte al borde vw .
Regresar F

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 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 puede ser modificada para comenzar con cualquier vértice particular, s estableciendo C [ s ] a ser un número más pequeño que los otros valores de C (por ejemplo, cero), y se puede modificar para encontrar solamente un único árbol de expansión en lugar de un bosque en expansión 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 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 del tiempo

Reproducir medios

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 de tiempo 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 usando una cola de prioridad . La siguiente tabla muestra las opciones típicas:

Estructura de datos de peso mínimo del borde	Complejidad de tiempo (total)
matriz de adyacencia , búsqueda	${\ Displaystyle O (\| V \| ^ {2})}$
montón binario y lista de adyacencia	${\ Displaystyle O ((\| V \| + \| E \|) \ log \| V \|) = O (\| E \| \ log \| V \|)}$
Lista de adyacencia y montón de Fibonacci	${\ Displaystyle O (\| E \| + \| V \| \ log \| V \|)}$

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 un tiempo de ejecución de O (| V | ² ). Sin embargo, este tiempo de ejecución se puede mejorar mucho más 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 usa 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 de O (| E | log | E |). 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 conecte a cualquier vértice en el árbol de expansión mínimo parcialmente construido (MST) (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 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 ).

Usando una estructura de datos de pila binaria simple , ahora se puede mostrar 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 que | E | es ω (| V |), y el tiempo lineal cuando | E | es al menos | V | log | V |. Para gráficos de densidad aún mayor (que tienen al menos | V | ^c bordes para algunos c > 1), se puede hacer que el algoritmo de Prim se ejecute en tiempo lineal de manera aún más simple, utilizando un montón d -ary en lugar de un montón de Fibonacci.

Demostración de la prueba. En este caso, el gráfico de 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 una gráfica ponderada conectada . En cada iteración del algoritmo de Prim, se debe encontrar un borde que conecte un vértice en un subgrafo con un vértice fuera del subgrafo. Dado que P está conectado, 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 el primer borde agregado durante la construcción del árbol Y que no está en el árbol Y ₁ , y V sea el conjunto de vértices conectados por los bordes agregados antes del borde e . Entonces, un extremo 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 _{1 que} une los dos puntos finales. Como uno viaja a lo largo de la ruta, hay que encontrar un borde f unirse a un vértice en el conjunto V a uno que no está en conjunto V . Ahora, en la iteración cuando se agregó el borde e al árbol Y , el borde f también podría haberse agregado y se agregaría en lugar del borde e si su peso fuera menor que e , y dado que el borde f no se agregó, concluimos que

{\ Displaystyle w (f) \ geq w (mi).}

Sea el árbol Y ₂ la gráfica obtenida quitando la arista f y agregando la arista e al árbol Y ₁ . Es fácil mostrar que el árbol Y ₂ está conectado, tiene el mismo número de aristas que el árbol Y ₁ y el peso total de sus aristas no es mayor que el del árbol Y ₁ , por lo tanto, también es un árbol de expansión mínima del gráfico. P y contiene borde e y todos los bordes añadidos antes de que durante la construcción del conjunto V . Repetir los pasos anteriores y que finalmente obtendremos un árbol de expansión mínimo de la gráfica P que es idéntico al árbol de 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 en un subconjunto X más pequeño , que suponemos es el mínimo.

Algoritmo paralelo

La matriz de adyacencia distribuida entre múltiples procesadores para el algoritmo de Prim 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. A continuación, se recopilan los resultados y se selecciona globalmente el siguiente vértice para incluir en el MST.

El bucle principal del algoritmo de Prim es inherentemente secuencial y, por lo tanto, no se puede paralelizar . 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. El siguiente pseudocódigo demuestra esto.

Asigne a cada procesador un conjunto de vértices consecutivos de longitud . ${\ Displaystyle P_ {i}}$ ${\ Displaystyle V_ {i}}$ ${\ Displaystyle {\ tfrac {| V |} {| P |}}}$
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. Let , denotan las partes de C , E almacenada en el procesador . ${\ Displaystyle C_ {i}}$ ${\ Displaystyle E_ {i}}$ ${\ Displaystyle P_ {i}}$
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. 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 todos los procesadores.
4. Añadir v a F y, si E [ v ] no es el valor especial de la bandera, también se suman E [ v ] para F .
5. En cada procesador: actualización y como en el algoritmo secuencial. ${\ Displaystyle C_ {i}}$ ${\ Displaystyle E_ {i}}$
Regresar F

Este algoritmo generalmente se puede implementar en máquinas distribuidas, así como en máquinas de memoria compartida. También se ha implementado en unidades de procesamiento gráfico (GPU). El tiempo de ejecución es , asumiendo que las operaciones de reducción y difusión se pueden realizar en . También se ha explorado una variante del algoritmo de Prim para máquinas de memoria compartida, en el que el algoritmo secuencial de Prim se ejecuta en paralelo, comenzando desde diferentes vértices. Sin embargo, debe tenerse en cuenta 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

El algoritmo de Dijkstra , un algoritmo muy similar para el problema de la ruta más corta
Los Greedoids ofrecen una forma general de comprender la exactitud del algoritmo de Prim.

Referencias

enlaces externos

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

Languages

In other projects