Algoritmo De PRIM

Índice

CONTENIDO Página

INTRODUCCIÓN……………………………………………………………………………………….........................…… 3

ALGORITMO DE PRIM..................................................................………................................. 4

CONCLUSIÓN ............................................................................................................... ....... 12

BIBLIOGRAFÍA ............................................................................................................................ 13

INTRODUCCIÓN

El hombre siempre ha tenido la necesidad de recorrer muchos lugares, utilizando caminos estratégicos y cortos buscando hallar la ruta optima con el mayor ahorro de tiempo, energía, distancia, etc. recorriendo todos los puntos designados.

En la actualidad podemos apreciar muchas cosas que nos pueden parecer de lo más habitual, caminos, líneas de comunicación telefónica, televisión por cable, el transporte ferroviario, líneas de aéreas, circuitos eléctricos de nuestras casas, automóviles, etc; lo que no pensamos frecuentemente es que estos formen parte de algo que en matemáticas se denomina como grafos.

En esta monografía se explicara el Algoritmo de Prim, buscando aplicarlo en problemas reales y cotidianos, utilizando en general la Teoría de Grafos.

ALGORITMO DE PRIM

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 de Marh Center (Bell Labs) fueron los prioneros de la moderna teoría de secuenciación, particularmen en el análisis de algoritmos de aproximación y en secuenciación multiprocesador (Ed Coffman, Ron Graham, David Johnson y Mike Garex). 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 algotitmo 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 quásar, plegamiento de proteínas, reconocimiento de células cancerosas, y otros). También se ha utilizados 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 al 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.

Un grafo o grafica es un conjunto finito de nodos o vértices conectados a través de aristas, los cuales pueden ser conexos, es decir existe algún enlace con cada nodo a través de algún camino formando así un grafo entero; O los grafos no conexos, que tienen la particularidad de que un segmento de grafo no este enlazado a través de algún vértice al grafo principal. En la teoría de grafos existen grafos dirigidos y grafos no dirigidos , lo grafos dirigidos son aquellos donde sus aristas tienen un sentido , quiere decir que tienen un principio especifico en algún nodo y un destino en algún otro a diferencia de los no dirigidos que son solo grafos simples (puede tomar ambas direcciones).

Árboles, un árbol es un grafo que no contiene ciclos y que conecta todos los nodos utilizando el menor número de aristas posibles.

Árbol recubridor mínimo,

...