domingo, 16 de mayo de 2010

Proyecto # 5



El Tema que yo elegi para mi 5to proyecto y ultimo es Camino mas Largo: Programacion Dinámica.

Principalmente
En teoría de los grafos [ grafos como nosotros ya sabemos es una representación mediante una serie de puntos (vértices) conectados por lineas (aristas) ], el problema de " El camino mas largo"
es dado un grafo, encontrar un camino simple de longitud maxima.

A diferencia de el problema camino mas corto que se puede solucionar en tiempo polinomial, pero este problema es NP- completo lo que quiere decir que la solución optima no se puede encontrar en tiempo polinomico.

Un problema Completo es aquel:
  • Que todos los demas problemas de la clase se reducen.
  • son los problemas más dificiles (en el hecho de que son mas largos)
Tambien este tema esta muy relacionado con Programación Dinámica

El matemático Richard Bellman inventó la programacion dinamica en 1953.

Almacenar los resultados en una tabla, empezando por los tamaños pequeños y avanzando hacia los mas grandes.

Ademas es un metodo para reducir el tiempo de ejecucion de un algoritmo mediante la utilizacion de subproblemas superpuestos y subestructuras optimas (significa que se pueden usar soluciones optimas de subproblemas para encontrar la solucion optima de problema en su conjunto).

En general se pueden resolver problemas con subestructuras optimas siguiendo estos tres pasos:
  • Dividir el problema en subproblemas mas pequeños
  • Resolver estos problemas de manera optima usando este proceso de tres pasos recurrentes
  • Usar estas soluciones optimas para construir una solucion optima al problema original.
Los subproblemas se resuelven a su vez dividiendolos en subproblemas mas pequeños hasta que se alcance el caso facil, donde la solucion al problema sea trivial.

La programacion dinamica es un metodo ascendente, se resuelven primero los sub ejemplares mas pequeños y por tanto mas simples. combinando las soluciones se obtienen las soluciones de ejemplares sucesivamente mas grande hasta llegar al ejemplar original.

Un ejemplo de camino largo puede ser
  • Sucesion de Fibonacci

esta expresion puede expresarse mediante la siguiente recurrencia:

Fib(n)=

0 si n=0
1 si n=1
Fib(n-1)+ Fiib(n-2) si n>1

INICIO

SI n = 0 ENTONCES

DEVOLVER 0

SINOSI n = 1 ENTONCES

DEVOLVER 1

SINO

devolver fib(n-1) + fib(n-2)

FINSI

FIN

Si llamamos, por ejemplo, a fib(5), produciremos un árbol de llamadas que contendrá funciones con los mismos parámetros varias veces:

  1. fib(5)
  2. fib(4) + fib(3)
  3. (fib(3) + fib(2)) + (fib(2) + fib(1))
  4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
  5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

En particular, fib(2) se ha calculado dos veces desde cero. En ejemplos mayores, se recalculan muchos otros valores de fib.

Para evitar este inconveniente, podemos resolver el problema mediante programación dinámica, y en particular, utilizando el enfoque de memorización (guardar los valores que ya han sido calculados para utilizarlos posteriormente). Así, rellenaríamos una tabla con los resultados de los distintos subproblemas, para reutilizarlos cuando haga falta en lugar de volver a calcularlos. La tabla resultante sería una tabla unidimensional con los resultados desde 0 hasta n.

Con programacion Dinamica
operacion fibonacci(n:entero): entero
T[1]:=1;T[2]:=1
para i:=3,......,n hacer
T[i]:= T[i-1]+T[i-2]
devolver T[n]

Cabe mencionar unos metodos como conclusión sobre este tema:

Metodo descentente

  • Empezar con el problema original y descomponer recursivamente en problemas de menor tamaño.
  • Partiendo del problema grande, descendemos hacia problemas más sencillos.

Metodo ascendente
  • Resolvemos primero los problemas pequeños (guardando las soluciones en una tabla). Después los vamos combinando para resolver los problemas más grandes.
  • Partiendo de los problemas pequeños avanzamos hacia los más grandes.
Antes de mi autoevaluacion quiero subir una parte en la que falle en la exposicion de mi tema que fue lo que la maestra elisa me pidio que realizara en el momento en el que me dijo pues no pude hacerlo pero ya cuento ella lo empezo recordo que esas tablas me las acababan de enseñar en mi clase de matematicas discretas quiero poner el ejemplo :
poniendo un grafo como el de la imagen poder realizar la tabla de la que les hable que se realiza con programacion dinamica

a continuacion la tabla

Bueno solo queria agregar eso para que quedara mas claro.

Autoevaluacion:
En mi opinion eh aprendido mucho de este curso puede que no me esta llendo perfecto pero se que tengo concimientos nuevos e interesantes, bueno anfocandome en este ultimo proyecto me puse muy nerviosa al exponer mi clase es por falta de seguridad y de saber el tema estoy de acuerdo en eso pero con todo y nervio pude exponerla. En esta clase aprendi a lo diferente de trabajar sola y en equipo y lo importante de eso, me falta poner mas de mi parte en cada punto de mis tareas es en lo que fallo.
Deseo la mejor de la suerte a todos.
cualquier duda con confianza pueden preguntarme :D










5 comentarios:

  1. quisiera saber que aplicaciones tiene .

    Para que es conveniente usarlo.

    espero y me puedas reposnder , grasias

    http://doranellygonzalez.blogspot.com/

    ResponderEliminar
  2. hola soy joel de la clase de jueves, me parecio muy buena el ejemplo que diste de la serie de Fibonacci con eso creo que quedo muy claro tambien queria preguntar en que podemos utilizar este algoritmo en nuestra vida diaria ?

    ResponderEliminar
  3. Hola claudia estuve observando tu blog y me parecio bastante interesante.Lo que me entro un poco de curiosidad fue de que estabas llamando fib(5)y al hacer eso producias un arbol, mi pregunta ¿Como podrias representar ese arbol?
    y tambien la duda sobre alguna aplicacion en la cual tenga este problema en lo cotidiano.
    Espero me puedas responder.
    Saludos!

    ResponderEliminar
  4. Que onda Claudia, pues este algoritmo de programacion dinamica, segun entiendo yo tiene que ver mucho con la recursividad, ya que para resolver determinado problema se desglosa en problemas mas simples hasta obtener una basee de la cual partir para resolver el problema, y tambien me gustaria saber en que puedo aplicar esto o como lo podemos observar en la vida diaria este algoritmo, :D

    ResponderEliminar
  5. Bueno, ya pusiste la tabla INICIAL de comenzar buscar el camino mas largo, pero en ningún momento lo buscas. Luego seguiría el algoritmo en sí. Una solución sería que reemplaces cada costo c por -c y luego comienzas a buscar por el camino más barato con un algoritmo que admite pesos negativos. En general el problema es NP completo pero si lo restringes a grafos dirigidos acíclicos (los llamados DAG), existe un algoritmo eficiente de programación dinámica que es lo que yo esperaba que presentes y que des un ejemplo de ello.

    El algoritmo para DAGs viene hasta en Wikipedia (http://en.wikipedia.org/wiki/Longest_path_problem) y está basado en el ordenamiento topológico que se presentó también.

    ResponderEliminar