algoritmo de Prim
árbol de coste total mínimo/máximo
Robert Prim en 1957 descubrió un algoritmo para la resolución del problema del Árbol de coste total mínimo (minimum spanning tree - MST). Este problema es un problema típico de optimización combinatoria, que fue considerado originalmente por Otakar Boruvka en 1926 mientras estudiaba la necesidad de electrificación rural en el sur de Moravia en Checoslovaquia. Este problema también fue resuelto por Joseph B. Kruskal en 1956.
En los años 60 estos científicos del Math Center (Bell Labs) fueron los pioneros de la moderna teoría de secuenciación, particularmente en el análisis de algoritmos de aproximación y en secuenciación multiprocesador (Ed Coffman, Ron Graham, David Johnson y Mike Garey). En las siguientes tres décadas, se añadieron multitud de contribuciones que mejoraron la teoría general.
El algoritmo de Prim encuentra un árbol de peso total mínimo conectando nodos o vértices con arcos de peso mínimo del grafo sin formar ciclos.
Al igual que el algoritmo de Kruskal, el de Prim también ha sido aplicado para hallar soluciones en diversas áreas (diseño de redes de transporte, diseño de redes de telecomunicaciones - TV por cable, sistemas distribuidos, interpretación de datos climatológicos, visión artificial - análisis de imágenes - extracción de rasgos de parentesco, análisis de clusters y búsqueda de superestructuras de quasar, plegamiento de proteínas, reconocimiento de células cancerosas, y otros). También se ha utilizado para encontrar soluciones aproximadas a problemas NP-Hard como el del 'viajante de comercio'.
algoritmo de Prim (árbol de coste total mínimo)
Consiste en dividir los nodos de un grafo en dos conjuntos: procesados y no procesados. Al principio, hay un nodo en el conjunto procesado que corresponde a el equipo central; en cada interacción se incrementa el grafo de procesados en un nodo (cuyo arco de conexión es mínimo) hasta llegar a establecer la conexión de todos los nodos del grafo a procesar. A continuación se muestra el pseudocódigo del algoritmo:
Prim ( L [1..n , 1..n ]) : 'conjunto de arcos
'Inicialización: sólo el nodo 1 se encuentra en B
T =NULL 'T contendrá los arcos del árbol de extensión mínima Distmin[1]=-1
para i=2 hasta n hacer
más_próximo [ i ]=1
distmin [ i ]=L [ i , 1]
para i=1 hasta n -1 hacer
min=infinito
para j=2 hasta n hacer
si 0 <= distmin [ j ] < min entonces
min=distmin [ j ]
k=j
T=T union {{mas_próximo [ k ], k }}
distmin [ k ]= -1 'se añade k a B
para j=2 hasta n hacer
si L [ j , k ] < distmin [ j ] entonces
distmin [ j ]=L [ j , k ]
más_próximo [ j ]=k
devolver T
Algunos trabajos han comparado la eficiencia entre los algoritmos de Kruskal y de Prim:
Sea a es el número de arcos y n el número de nodos. El algoritmo de Kruskal requiere un tiempo que está en O(a log n). Para un grafo denso, a tiende a n(n-1)/2, por lo que el algoritmo requiere un tiempo que está en O(n^2 log n), y el algoritmo de Prim puede ser mejor O(n^2). En un grafo disperso, a tiende a n-1, por lo que el algoritmo de Kruskal requiere un tiempo que está en O(n log n) y el algoritmo de Prim es menos eficiente. Sin embargo, si el algoritmo de Prim se implementa con montículos, el tiempo requerido por este algoritmo está, como el de Kruskal, en O(a log n).
- Si a es aproximadamente igual a n (grafo con pocos arcos) conviene usar Kruskal
- Si a es aproximadamente igual a n^2 (grafo denso) conviene usar Prim
En cualquier caso, la complejidad del algoritmo de Kruskal depende de la técnica de ordenación empleada. El algoritmo de Prim requiere más memoria que el algoritmo de Kruskal. Ambos algoritmos son relativamente fáciles de paralelizar. Puede encontrar más información en:
- R.C. Prim, Shortest connection networks and some generalizations, Bell System Technical Journal, 36, pp. 1389-1401, 1957.