Algoritmo de prim

Check out this SlideShare Presentation:

Algoritmo de prim

View more presentations from Abraham.

Reporte del Proyecto 5 Algoritmo de Prim

Un poco acerca de esto:

El algoritmo de prim es un algoritmo perteneciente a la teoría de lo grafos para encontrar un árbol recubridor mínimo en un grafo conexo , no dirigido y cuyas aristas están etiquetadas.

El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik.

pero para no aburrirte tanto acerca de este, en pocas palabras lo que hace es que que ayuda a ahorrar recursos, llegando a cada una de sus aristas.

Problema que resuelve

El problema que resuelve es del camino mas corto o caminos minimos. El problema consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínima.

Problema de decision:

Existe un camino mas corto que c?

Respuesta: La pregunta que se te hace es que si existe un camino mas corto, si la respues es que si, ya sea de que a o b sean mas cortos que c, y se vuelve a hacerse la misma pregunta pero ahora si hay uno de b, ya que puede haber un d o un e, cuando la respuesta sea no y haya recorrido todas las aristas, la solucion habra acabado.

Perteneciente a P

Este problem se puede resolver en timpo polinomial, por lo tanto esto se puede resolver con una maquina turing no determinsita en timpo polinomial

Algoritmo:

los pasos son:

1. Se marca un nodo cualquiera, será el nodo de partida.

2. Seleccionamos la arista de menor valor incidente en el nodo marcado anteriormente, y marcamos el otro nodo en el que incide.

3. Repetir el paso 2 siempre que la arista elegida enlace un nodo marcado y otro que no lo esté.

4. El proceso termina cuando tenemos todos los nodos del grafo marcados.

Que es lo que viene haciendo esta algoritmo?

lo que viene haciedno este algoritmo es, recorrer todo el grafo dado, tocando cada una de sus aristas, utilizando el menor numero posible de reursos.

Pseudocodigo

// Inicializamos todos los nodos del grafo. La distancia la ponemos a infinito y el padre de cada nodo a NULL

// Encolamos, en una cola de prioridad donde la prioridad es la distancia, todas las parejas del grafo

por cada u en V[G] hacer

distancia[u] = INFINITO

padre[u] = NULL

Añadir(cola,)

distancia[s]=0

mientras cola != 0 do

// OJO: Se entiende por mayor prioridad aquel nodo cuya distancia[u] es menor.

u = extraer_minimo(cola) //devuelve el minimo y lo elimina de la cola.

por cada v adyacente a 'u' hacer

si ((v ∈ cola) && (distancia[v] > peso(u, v)) entonces

padre[v] = u

distancia[v] = peso(u, v)

Actualizar(cola,)

Ejemplo paso a paso:

Siguiendo el algoritmo de Prim, tenemos:

o Elegimos, por ejemplo, el nodo 1 y lo marcamos.

o Elegimos la arista con menor valor incidente en 1, la (1, 3) = 1 la marcamos y marcamos el otro nodo en el que incide, el 3.

o Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (1, 2) = 3 la marcamos y marcamos el nodo no marcado, el 2.

o Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (2, 5) = 5 la marcamos y marcamos el nodo no marcado, el 5.

o Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 6) = 1 la marcamos y marcamos el nodo no marcado, el 6.

o Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 7) = 2 la marcamos y marcamos el nodo no marcado, el 7.

o Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 4) = 6 la marcamos y marcamos el nodo no marcado, el 4.

o FIN. Finalizamos dado que tenemos marcados los 7 nodos del grafo.

o Por tanto el árbol de mínima expansión resultante sería:

Estructura de datos:

El tipo de estrucura de datos, que este emlpea es el de cola de prioridad, ya que se van a indicando conforme a su prioridad.

Su complejidad:

Es O(n^2), porque se recorre cada nodo y se compara con cada uno de ellos, para marcarlos que ya los visito, y asi no usar mas recursos.

Aplicaciones

Este algoritmo tiene diversas aplicaciones, mas que nada es impementado, para ahorrar recursos como ya se habia mencionado, se puede usar en el cableado en poner postes de luz, cableados de redes, entre otros.

como viene funcionando esto?

imaginate, si cada poste de luz es un nodo junto tambien con las casas, y su cableado es un arista y a esta asignandole un valor, que viene siendo la distancia que hay en ellos, para esto hay que buscar la forma en ahorra cableado, para eso se emplea este algoritmo.

Bibliografia:

http://es.wikipedia.org/wiki/Algoritmo_de_Prim

http://algoritmoshade.blogspot.com/

http://www.cut-the-knot.org/Curriculum/Games/Mazes.shtml

http://www.youtube.com/results?search_query=algoritmo+de+prim&aq=0

http://www.mincel.com/java/prim.html