LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

el algoritmo de Prim(también conocido como Jarník ) es un algoritmo codicioso que encuentra un árbol de expansión mínimopara un gráfico no dirigido ponderado . Esto significa que encuentra un subconjunto de los bordes que forma un árbol que incluye cada vértice , donde se minimiza el peso total de todos los bordes en el á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 el matemático checo Vojtěch Jarník ^[1] y posteriormente redescubierto y publicado por los científicos informáticos Robert C. Primen 1957 ^[2] y Edsger W. Dijkstra en 1959. ^[3] Por lo tanto, a veces también se le llama El algoritmo de Jarník , ^[4]El algoritmo ^de Prim – Jarník , ^{[5] El} algoritmo de Prim – Dijkstra ^[6] o el algoritmo de 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í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ínima 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. ^[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 los gráficos que son lo suficientemente densos, el algoritmo de Prim puede ejecutarse en tiempo lineal , cumpliendo o mejorando los límites de tiempo para otros algoritmos.

Descripción [ editar ]

El algoritmo puede ser descrito informalmente realizando los siguientes pasos:

1. Inicialice un árbol con un solo vértice, elegido arbitrariamente de la gráfica.
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).

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

1. Asocie a cada vértice v del gráfico un número C [ v ] (el costo más barato de una conexión a v ) y un borde E [ v ] (el borde que proporciona la conexión más barata). Para inicializar estos valores, configure todos los valores de C [ v ] en + ∞ (o en cualquier número mayor que el peso máximo del borde) y configure cada E [ v ] en un valor de marca especial que indique que no hay ningún borde que conecte v al 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. Agregue v a F y, si E [ v ] no es el valor del indicador especial, también agregue E [ v ] a F
   3. Recorra los bordes vw conectando v con otros vértices w . Para cada uno de estos bordes, si w aún 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. Establezca E [ w ] para apuntar al borde vw .
4. Volver f

Como se describió anteriormente, el vértice de inicio 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 todos 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 configurando C [ s ] a ser un número más pequeño que los otros valores de C(por ejemplo, cero), y puede modificarse para que solo encuentre un solo árbol de expansión en lugar de un bosque de expansión completo (que coincida más con la descripción informal) deteniéndose cada vez que encuentre otro vértice marcado como que no tiene borde asociado.

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 del tiempo 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 conllevará actualizaciones más costosas cuando cambie el valor de C [ w ].

Complejidad temporal [ editar ]

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

La complejidad del 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 del 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 |)}
Fibonacci montón y lista de adyacencia	$${\ displaystyle O (| E | + | V | \ log | V |)}

Una implementación simple de Prim, utilizando una matriz de adyacencia o una representación gráfica de lista de adyacencias y buscando linealmente una serie de ponderaciones para encontrar el borde de peso mínimo a agregar, requiere 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 utiliza un montón para almacenar todos los bordes del gráfico de entrada, ordenados por su peso. Esto lleva a un O (| E | log | E |) tiempo de ejecución 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 a la MST, se realiza una operación de reducción de teclas en todos los vértices w fuera de la MST parcial, de manera que v está conectada a w , estableciendo la clave al mínimo de su valor anterior y el costo de borde de ( v , w ).

Usando una estructura simple de datos del montón binario , 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 Fibonacci más sofisticado , esto puede reducirse 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 tiempo lineal cuando | E | es al menos | V | log | V |. Para gráficos de densidad aún mayor (con al menos | V | ^c bordes para algunos c > 1), el algoritmo de Prim puede ejecutarse en tiempo lineal aún más simple, usando una d-hermoso montón en lugar de un montón de Fibonacci. ^[10] [11]

Demostración de la prueba. En este caso, el gráfico de Y ₁ = Y - f + eya es igual a Y . En general, el proceso puede necesitar repetirse.

Prueba de corrección [ editar ]

Sea P un gráfico conectado y ponderado . En cada iteración del algoritmo de Prim, se debe encontrar un borde que conecte un vértice en un subgrafo a un vértice fuera del subgraph. 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 Yeso no está en el árbol Y ₁ , y V es el conjunto de vértices conectados por los bordes agregados antes del borde 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 _{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 el borde e se agregó al árbol Y , el borde fTambién se podría haber agregado y se agregaría en lugar del borde e si su peso fuera menor que e , y como no se agregó el borde f , concluimos que

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

Sea el árbol Y ₂ el gráfico obtenido al quitar el borde f y al agregar el borde e al árbol Y ₁ . Es fácil mostrar que el árbol Y ₂ está conectado, tiene el mismo número de bordes que el árbol Y ₁ , y el peso total de sus bordes no es mayor que el del árbol Y ₁ , por lo que también es un árbol de gráfico de expansión mínima. P y contiene borde e y todos los bordes añadió antes de que durante la construcción del conjunto V . Repita los pasos anteriores y eventualmente obtendremos un árbol de expansión mínimo del gráfico Pque 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 sub-región se expanda en un subconjunto más pequeño X , que asumimos como el mínimo.

Algoritmo paralelo [ editar ]

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 Cinspeccionando la fila del vértice recién insertado en su conjunto de columnas en la matriz de adyacencia. Los resultados se recopilan y el siguiente vértice para incluir en el MST se selecciona globalmente.

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

1. Asignar cada procesadores $${\ displaystyle P_ {i}} un conjunto $${\ displaystyle V_ {i}} de vértices consecutivos de longitud $${\ displaystyle {\ tfrac {| V |} {| P |}}}.
2. Cree C, E, F y Q como en el algoritmo secuencial y divida C, E, así como la gráfica entre todos los procesadores, de modo que cada procesador mantenga los bordes entrantes en su conjunto de vértices. Dejar$${\ displaystyle C_ {i}}, $${\ displaystyle E_ {i}}denota las partes de C , E almacenadas en el procesador$${\ displaystyle P_ {i}}.
3. Repita los siguientes pasos hasta que Q esté vacío:
   1. En cada procesador: encuentra el vértice. $${\ displaystyle v_ {i}} teniendo el valor mínimo en $${\ displaystyle C_ {i}}El$${\ displaystyle v_ {i}}] (solución local).
   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. Difunde el nodo seleccionado a cada procesador.
   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 $${\ displaystyle C_ {i}} y $${\ displaystyle E_ {i}} Como en el algoritmo secuencial.
4. Volver f

Este algoritmo generalmente se puede implementar en máquinas distribuidas ^[12] , así como en máquinas de memoria compartida. ^[13] También se ha implementado en unidades de procesamiento gráfico (GPU). ^[14] El tiempo de ejecución es$${\ displaystyle O ({\ tfrac {| V | ^ {2}} {| P |}}) + O (| V | \ log | P |)}, asumiendo que las operaciones de reducción y difusión se pueden realizar en$${\ displaystyle O (\ log | P |)}. ^[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, a partir de diferentes vértices. ^[15] Sin embargo, se debe tener 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.

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

algoritmo de borrado inverso es un algoritmo en la teoría de grafos que se utiliza para obtener un árbol de expansión mínimo a partir de un grafo conectado y ponderado de borde dado . Apareció por primera vez en Kruskal (1956) , pero no debe confundirse con el algoritmo de Kruskal que aparece en el mismo artículo. Si el gráfico está desconectado, este algoritmo encontrará un árbol de expansión mínimo para cada parte desconectada del gráfico. El conjunto de estos árboles de expansión mínima se llama un bosque de expansión mínimo, que contiene cada vértice en el gráfico.

Este algoritmo es un algoritmo codicioso , que elige la mejor opción en cualquier situación. Es el reverso del algoritmo de Kruskal , que es otro algoritmo codicioso para encontrar un árbol de expansión mínimo. El algoritmo de Kruskal comienza con un gráfico vacío y agrega bordes, mientras que el algoritmo de Revertir-Borrar comienza con el gráfico original y borra los bordes. El algoritmo funciona de la siguiente manera:

• Comience con el gráfico G, que contiene una lista de bordes E.
• Ir a través de E en orden decreciente de pesos de borde.
• Para cada borde, compruebe si eliminar el borde desconectará aún más el gráfico.
• Realice cualquier eliminación que no lleve a una desconexión adicional.

Pseudocódigo [ editar ]

1   función ReverseDelete (bordes [] E )
 2     tipo  E en orden decreciente
 3 Definir un índice i ← 0
 4     mientras  i < tamaño ( E )
 5 Definir borde ← E [ i ]
 6     borrar  E [ i ]
 7     si el gráfico no está conectado
 8              E [ i ] ← borde 
 9             i ← i + 1
 10    bordes de retorno [] E

En lo anterior, el gráfico es el conjunto de bordes E con cada borde que contiene un peso y vértices conectados v1 y v2 .

Ejemplo [ editar ]

En el siguiente ejemplo, los bordes verdes están siendo evaluados por el algoritmo y los bordes rojos se han eliminado.

	Este es nuestro gráfico original. Los números cerca de los bordes indican su peso de borde.
	El algoritmo comenzará con el borde máximo ponderado, que en este caso es DE con un peso de borde de 15. Ya que eliminar el borde DE no desconecta más el gráfico, se elimina.
	El siguiente borde más grande es FG, por lo que el algoritmo verificará si eliminar este borde desconectará aún más el gráfico. Dado que eliminar el borde no desconectará más el gráfico, el borde se elimina.
	El siguiente borde más grande es el borde BD, por lo que el algoritmo comprobará este borde y eliminará el borde.
	El siguiente borde a verificar es el borde EG , que no se eliminará ya que desconectaría el nodo G del gráfico. Por lo tanto, el siguiente borde a eliminar es el borde BC .
	El siguiente borde más grande es el borde EF, por lo que el algoritmo comprobará este borde y eliminará el borde.
	El algoritmo buscará los bordes restantes y no encontrará otro borde para eliminar; por lo tanto, este es el gráfico final devuelto por el algoritmo.

Tiempo de ejecución [ editar ]

Se puede mostrar que el algoritmo se ejecuta en O ( E log V (log log V ) ³ ) tiempo (utilizando la notación big-O ), donde E es el número de bordes y V es el número de vértices. Este límite se logra de la siguiente manera:

• La clasificación de los bordes por peso utilizando una ordenación de comparación lleva tiempo O ( E log E ), que se puede simplificar a O ( E log V ) utilizando el hecho de que la E más grande puede ser V ² .
• Hay iteraciones E del bucle.
• Eliminar un borde, verificar la conectividad del gráfico resultante y (si está desconectado) volver a insertar el borde se puede hacer en tiempo O (log V (log log V ) ³ ) por operación ( Thorup 2000 ).

Prueba de corrección [ editar ]

Se recomienda leer primero la prueba del algoritmo de Kruskal .

La prueba consta de dos partes. Primero, se demuestra que los bordes que permanecen después de que se aplica el algoritmo forman un árbol de expansión. En segundo lugar, se demuestra que el árbol de expansión tiene un peso mínimo.

Árbol de expansión [ editar ]

El subgráfico (g) restante producido por el algoritmo no se desconecta ya que el algoritmo verifica eso en la línea 7. El subgráfico de resultados no puede contener un ciclo, ya que si lo hace, al moverse a lo largo de los bordes, encontraremos el borde máximo. En el ciclo y eliminaríamos esa arista. Así, g debe ser un árbol de expansión del gráfico principal G.

Minimalidad [ editar ]

Se demuestra que la siguiente proposición P es cierto por inducción: Si F es el conjunto de aristas mantenido al final del bucle while, entonces hay algún árbol de expansión mínima (que sus bordes) son un subconjunto de F .

1. Claramente, P se mantiene antes del inicio del bucle while. dado que un gráfico conectado ponderado siempre tiene un árbol de expansión mínimo y como F contiene todos los bordes del gráfico, este árbol de expansión mínimo debe ser un subconjunto de F.
2. Ahora supongamos que P es cierto para algunos conjuntos de bordes no finales F y que T sea ​​un árbol de expansión mínimo contenido en F. debemos mostrar que después de eliminar el borde e en el algoritmo existen algunos (posiblemente otros) árboles de expansión T 'que es un subconjunto de F.
   1. Si el siguiente borde eliminado e no pertenece a T, entonces T = T 'es un subconjunto de F y P semantiene. .
   2. de lo contrario, si e pertenece a T: primero tenga en cuenta que el algoritmo solo elimina los bordes que no causan una desconexión en la F. así que e no causa una desconexión. Pero eliminar e provoca una desconexión en el árbol T (ya que es un miembro de T). supongamos que e separa T en los subgráficos t1 y t2. Dado que todo el gráfico está conectado después de eliminar e, debe existir una ruta entre t1 y t2 (que no sea e), por lo que debe existir un ciclo C en la F (antes de eliminar e). ahora debemos tener otra ventaja en este ciclo (llámelo f) que no está en T pero sí en F (ya que si todos los bordes de ciclo estuvieran en el árbol T, ya no sería un árbol). ahora afirmamos que T '= T - e + f es el árbol de expansión mínimo que es un subconjunto de F.
   3. En primer lugar, probamos que T 'es un árbol de expansión . lo sabemos al eliminar un borde en un árbol y al agregar otro borde que no causa un ciclo, obtenemos otro árbol con los mismos vértices. ya que T era un árbol de expansión, entonces T 'también debe ser un árbol de expansión . ya que agregar "f" no causa ningún ciclo desde que se eliminó "e" (tenga en cuenta que el árbol T contiene todos los vértices del gráfico).
   4. En segundo lugar, probamos que T 'es un árbol de expansión mínimo . Tenemos tres casos para los bordes "e" y "f". wt es la función de peso.
      1. wt (f) ya que T es el árbol de expansión mínimo, esto es simplemente imposible.
      2. wt (f)> wt (e) esto también es imposible. desde entonces, cuando estamos atravesando bordes en orden decreciente de pesos de bordes, primero debemos ver "f". ya que tenemos un ciclo C, por lo que eliminar "f" no causaría ninguna desconexión en la F., por lo que el algoritmo lo habría eliminado de F antes. por lo que "f" no existe en F, lo cual es imposible (hemos comprobado que f existe en el paso 4.
      3. así que wt (f) = wt (e) así que T 'también es un árbol de expansión mínimo . así que de nuevo p tiene
3. así que P se mantiene cuando se realiza el ciclo while (que es cuando hemos visto todos los bordes) y al final probamos que F se convierte en un árbol de expansión y sabemos que F tiene un árbol de expansión mínimo como su subconjunto. entonces F debe ser el árbol de expansión mínimo en sí mismo.