sábado, 15 de mayo de 2010

Proyecto 5

Reporte del Proyecto 5
Tema: Algoritmo de Dijkstra: Caminos minimos












Descripción:

El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo no dirigido y con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.

Esto es que basicamente, el algoritmo busca desde un nodo o vertice dado, el camino mas corto a todos los demas nodos, ya que este encuentra los caminos mas cortos, se detiene.

El algoritmo de Dijkstra es un tipo de algoritmo voraz, que es aquel que para resolver un problema,elige la opción más óptima en cada paso para asi poder llegar a la solucion optima. 

Cabe destacar que para que el algoritmo funcione, sus pesos en las aristas deben ser positivos, ya que en caso de se negativos se caería en un ciclo infinito.


Problema que resuelve:

El algoritmo de Dijkstra resuelve el problema del camino más corto o caminos mínimos.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 decisión:   

Existe un camino mas corto que L?

Explicación: Es sencillo. la pregunta te dice si hay un camino mas corto que L, la respuesta sera un si o un no. Si la respuesta es un si, entonces hay un camino mas corto que L, y se vuelve a preguntar hasta que la respuesta sea no. Cuando sea no, la solución se abra optimizado. 

Pertenece a P

El problema del camino mas corto, o shortest path problem, se puede resolver en tiempo polinomial, mientras los pesos o distancias del grafo no sean negativos. Por lo tanto puede ser resuelto por una maquina turing determinista en tiempo polinomial.

Algoritmo:

El algoritmo nos optimiza los caminos que hemos de recorrer entre nodos en un grafo no dirigido. Seguramente podríamos llegar de un nodo a otro por varios caminos, pero lo que nos interesa es llegar por el menor de los caminos.

1) Seleccionamos el nodo no visitado con menor distancia acumulada( S

2) Sumamos la distancia acumulada en dicho nodo con la distancia de las aristas a los nodos a los que podemos acceder. Comparamos la nueva distancia con la que teníamos acumulada en el nodo destino (en caso de tener ya alguna) y nos quedamos con la menor. 

3) Marcamos el nodo actual como visitado y volvemos al paso 1.

Así obtendremos las distancias mínimas a un nodo dado.

Explicación:
Basicamente lo que hace el algoritmo es recorrer todo el grafo. Primero desde el origen, se exploran los caminos posibles a otros vértices, entonces se suman los costos para llegar a cada vértice, y se coloca el número sobre el vértice. En caso de que ya tenga un costo, si este es mayor al nuevo costo, se actualiza, quedandose con el nuevo. Así se pueden obtener las distancias mas cortas a todos los vértices desde el origen.
Pseudocodigo

DIJKSTRA (Grafo G, nodo_fuente s)       
       for uV[G] do
           distancia[u] = INFINITO
           padre[u] = NULL
       distancia[s] = 0
       Encolar (cola, grafo)
       mientras cola no es vacía do          
           u = extraer_minimo(cola)
           for v ∈ adyacencia[u] do
               if distancia[v] > distancia[u] + peso (u, v) do
                   distancia[v] = distancia[u] + peso (u, v)
                   padre[v] = u

Éste pseudocodigo es para el algoritmo de Dijkstra, usando cola de prioridad.

Ejemplo paso a paso:

Se buscara el camino mas corto desde "a" hasta "z".Aunque el algoritmo busca el camino mas corto a todos los vertices,tambien se puede utilizar el mismo algoritmo para encontrar el mas corto a cualquier otro punto, lo haremos solo hasta z para entender como funciona.












*Se pintaran con rojo las aristas y vertices pertenecientes a la solucion momentanea.
*Y con azul las aristas y vertices candidatos (a los que se puede hacer un movimiento).











1- En el primer paso hay 3 vertices candidatos desde a,estos son: b, c, d. Y se realiza el camino hacia d ya que es el caminos mas corto  de los 3. Entonces:
Solucion momentanea:
Camino a-d   Distancia: 5










2- En el segundo paso, los candidatos son c y e (sin tomar en cuenta a por logica), entonces escoje el mas corto de esos 2, que viene siendo el c.
Solucion momentanea:
Camino a-d-c.   Distancia: 9










3- En el tercer paso, los candidatos son b y f,entonces se scoje de nuevo el de menor distancia, b.
Solucion momentanea:
Camino: a-d-c-b  Distancia: 11










4- En el paso 4, los candidatos son f y g, se procede a escojer el camino mas corto,f.
Solucion momentanea:
Camino: a-d-c-b-f.   Distancia: 15











5-En el paso 5, los candidatos son z y e, con respecto a f. Se escoje el mas corto que es e.
Solucion momentanea:
Camino:a-d-c-b-f-e   Distancia: 18










6- En el paso 6 se tiene solo un canidato, z, entonces el camino final y minimo obtenido es:
Solucion final:
Camino: a-d-b-f-e-z    Distancia: 23

Estructura de Datos utilizada:

Este algoritmo utiliza un tipo de estructura de colas llamado cola de prioridad.Una cola de prioridad es una estructura de datos en la que los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen.
Un ejemplo en la vida diaria de ésto seria la sala de urgencias de un hospital, ya que los enfermos se atienden en orden a la gravedad de sus enfermedades o heridas.

Complejidad

  •  La complejidad es O(n^2), ya que recorremos cada nodo una vez y comparamos cada uno de ellos con el resto para ver si ya estaba visitado o para calcular distancias. Esto sin utilizar cola de prioridad.


  • O((|E|+|V|) log |V|) utilizando cola de prioridad (por ejemplo un montículo).

Aplicaciones:

  • Este algoritmo se usa bastante en redes de computadores, los nodos corresponden a routers y las aristas entre ellos las conexiones, a cada conexion se le asigna un costo (distancia) y de esta manera algunos protocolos de enrutamiento usan el algoritmo de Dijkstra para encontrar la mejor ruta entre nodos
  • Los algoritmos de los caminos más cortos se aplican para encontrar direcciones de forma automática entre localizaciones físicas, tales como direcciones en mapas callejeros.

    Presentación:

    .::Descargar::.

    Bibliografía:


    http://156.35.31.178/wiki/index.php/TP:Algoritmo_de_Dijkstra_-_Algoritmos_voraces
    http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra
    http://www.slideshare.net/joemmanuel/algoritmo-de-dijkstra
    http://neo.lcc.uma.es/evirtual/cdd/applets/distancia%20corta/Example2.html
    http://en.wikipedia.org/wiki/Shortest_path_problem


    P. D. Cualquier duda o pregunta que tengan sobre el tema pueden hacerla en los comentarios sin problema e intentare contestarla de la mejor  manera posible
    Saludos.

    13 comentarios:

    1. Autoevaluación: Al principio tuve problemas para entender el algoritmo. Pero despues note que era parecido al Problema del Viajante que ya habia estudiado con un algoritmo voraz, esto al lado de un video de youtube me ayudaron mucho a comprender como aplicarlo en una forma muy sencilla.
      Considero que es un algoritmo sencillo de entender.
      Acerca del reporte pienso que me quedo bien, gracias a que habia mucha informacion para entender el tema.

      ResponderEliminar
    2. Al tener una complejidad de O(n^2) es un mal algoritmo?

      ResponderEliminar
    3. Me gusto este tema se me hace muy aplicable a la vida diaria y es muy optimo utilizar este algoritmo, de echo yo presente algo de este tema para puntos extras el martes. Buen tema (Y)

      ResponderEliminar
    4. P.D. Dale una checadilla a mi blogg, tambien es interesante (y)

      ResponderEliminar
    5. Respuesta a yeyohbk:
      La complejidad n^2 no es mala, es mas o menos regular, pero utilizando la cola de prioridad se convierte en nlogn que es bastante buena asi que es un buen algoritmo, pero para pesos o valores en aristas, positivos.
      Saludos.

      ResponderEliminar
    6. Respuesta a Ricky Tover:
      Gracias por el comentario.Me daré una vuelta por tu blog.
      Saludos.

      ResponderEliminar
    7. Saludos!! una duda Como el algortimo resuelve el shortest path problem, cuando encuetras el camino mas corto a un nodo ya se termina? o se puede a mas vertices?

      ResponderEliminar
    8. Para Emilio:
      Hola, bueno la función del algoritmo es encontrar los caminos mas cortos a todos los vértices de un grafo, desde el vértice que se tome como inicial, es decir en si el algoritmo se detiene hasta terminar todos los vértices. Pero uno puede solo utilizarlo para obtener el camino hasta 1 solo vértice. Pero deben ser distancias o pesos positivos, no negativos.
      Saludos

      ResponderEliminar
    9. con el video que pusiste fue mas facil enter todo el coencepto

      recuerdo bien que fue lo que nos explicaste en clase.

      sabes en la clase yo te habia entendido que los pesos podian ser negativos , y me quede pensando sobre eso ,que bueno que leir tu blog para ver que fui yo la que escuche mal.

      Y en ese momento no te pregunte porque recuerdo que no habia tiempo y que si teniamos dudas tre las preguntarmos por el blog

      ResponderEliminar
    10. olvide poner algo que me identificara como nos menciona la maestra

      http://doranellygonzalez.blogspot.com/

      ResponderEliminar
    11. Respuesta a dora nelly:
      Gracias por el comentario, me alegra que fuera de ayuda el reporte y el video para que se entendiera el algoritmo.
      Saludos.

      ResponderEliminar
    12. Respuesta a tu pregunta:

      Bueno aqui les va la respuesta a la duda que tenian de la aplicacion de la ordenacion topologica en el analisis semantico de un complilador.
      Bueno primero para empezar, hay que identificar a lo que nos referimos con "Evaluacion Semantica de un Compilador":

      Evaluacion---Algo que se tiene a prueba.
      Semantica---Se refiere al significado ó sentido de algun elemento.
      Compilador---Es un programa que interpreta o traduce un lenguaje de programacion.

      Entonces ya juntos la frase se refiere a que "evalua si el significado de determinado proceso de algún algoritmo pertenesca al conjunto y lo pueda traducir.

      Entonces lo que hace la ordenacion topologica, es comprobar que los argumentos que tiene un operador pertenecen al conjunto de los operadores.
      En definitiva, comprobará que el significado de lo que se va leyendo es válido.
      La salida de la fase de análisis semántico sería un árbol semántico. Consiste en un árbol sintáctico en el que cada una de sus ramas ha adquirido el significado que debe tener. En el caso de los operadores polimórficos el análisis semántico determina cuál es el aplicable.

      Espero haberles resuleto la duda, si de igual forma sigen sin entenderlo, con toda confianza, pregunten sus dudas y yo las responere. Gracias por los comentarios.

      ResponderEliminar
    13. Muy bien. Como respuesta a Tadeo, un algoritmo O(n^2) es en algunos problemas lo mejor que se puede hacer, pero si checas para valores de n tipo 1, 10, 100, 1000, 10000, te das cuenta que crece rápidamente. Por ende, si existe algún otro algoritmo que sea por lo menos un poco mejor (por ejemplo O(n log n) u O(n^1.5) o cualquier cosa menor al cuadrado), la diferencia en eficiencia es significativa cuando n es mediano o grande.

      Los computólogos siempre buscan mejorar los algoritmos existentes y pensar en otros algoritmos innovativos con el fin de disminuir la complejidad asintótica del mejor algoritmo conocido.

      ResponderEliminar