lunes, 17 de mayo de 2010

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

7 comentarios:

  1. Hola, es sencillo el algoritmo, recorre y compara las distancias en pocas palabras, pero ¿hay una forma de que no recorra todo el grafo para ahorrar aun mas recursos?

    ResponderEliminar
  2. Mira, la verdad lo que hace este es que empieza de un nodo compara los pesos de sus aristas, se va al de menor valor, para llegar a otro nodo, despues de ese nodo, compara las aristas del primer nodo al igual del segundo para llegar a un nuevo nodo, hasta llegar a todos los nodos...
    Y asi respondo a tu pregunta,en la que no recorre todo el grafo, solo las aristas de menor valor para llegar a los nodos...
    Gracias por preguntar.
    Si tienes otra duda o pregunta, hasmela saber...
    saludos

    ResponderEliminar
  3. Muy bueno, fácil de entender porque explicaste bien y me toco el algoritmo de Dijkstra. Además las aplicaciones que pusiste son excelentes y no las había pensado. Felicidades.
    Saludos.

    ResponderEliminar
  4. Que otro uso se le puede dar aparte del cableado de las companias que explicaste en clase?

    ResponderEliminar
  5. Yo sospecho que el segundo cuadrito gris con la arista de peso cinco deberia ser una animación, pero algo le pasó cuando lo metiste al blog y no se ve más que el primer cuadro :(

    ResponderEliminar
  6. Acerca de tu pregunta Rodolfo, este algoritmo sirve para ahorrar recursos, asi que, otro uso que podrias usar seria... Como que caminos tomar para llegar a cierto lugar, sin irse por el camino mas largo...

    ResponderEliminar
  7. Y si , gracias profesora, no me habia percatado bien de eso, tratare de arreglarlo, gracias...

    ResponderEliminar