PROYECTO 5 Caminos mas largos: Programacion dinamica

Definicion:

Programación dinámica: almacenar los resultados en una tabla, empezando por los tamaños pequeños y avanzando hacia los más grandes.

En teoría de grafos, el problema del camino más largo es, dado un grafo, encontrar un camino simple de longitud máxima. A diferencia del problema del camino más corto, que se puede solucionar en tiempo polinómico en grafos sin ciclos negativos, este problema es NP-completo, lo que quiere decir que la solución óptima no se puede encontrar en tiempo polinómico a menos que P=NP.

El problema del camino más largo tiene una solución de programación dinámica eficiente en un grafo dirigido acíclico utilizando selección topológica. También se puede solucionar en un grafo dirigido acíclico invirtiendo los pesos y utilizando el algoritmo de Bellman-Ford(este enfoque no funciona en general porque crea ciclos de peso negativo).

La programación dinámica toma normalmente uno de los dos siguientes enfoques:

• Top-down: El problema se divide en subproblemas, y estos se resuelven recordando las soluciones por si fueran necesarias nuevamente. Es una combinación de memorización y recursión.
• Bottom-up: Todos los subproblemas que puedan ser necesarios se resuelven de antemano y después se usan para resolver las soluciones a problemas mayores. Este enfoque es ligeramente mejor en consumo de espacio y llamadas a funciones, pero a veces resulta poco intuitivo encontrar todos los subproblemas necesarios para resolver un problema dado.

Ejemplo de caminos mas largo en pseudocodigo

SUCESION DE FIBONACCI

Una implementación de una función que encuentre el n-ésimo término de la sucesión de Fibonacci basada directamente en la definición matemática de la sucesión realizando llamadas recursivas hace mucho trabajo redundante, obteniéndose una complejidad exponencial:

FUNC fib(↓n: NATURAL): NATURAL

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, o subproblemas.

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.

Un programa que calculase esto, usando Bottom-up, tendría la siguiente estructura:

FUNC Fibonacci (↓n: NATURAL): NATURAL

VARIABLES

tabla: ARRAY [0..n] DE NATURAL

i: NATURAL

INICIO

SI n <= 1 ENTONCES

devolver 1

SINO

tabla[0] ← 1

tabla[1] ← 1

PARA i ← 2 HASTA n HACER

tabla[i] ← tabla[i-1] + tabla[i-2]

FINPARA

devolver tabla[n]

FINSI

FIN

La función resultante tiene complejidad O(n), en lugar de exponencial.

Otro nivel de refinamiento que optimizaría la solución sería quedarnos tan sólo con los dos últimos valores calculados en lugar de toda la tabla, que son realmente los que nos resultan útiles para calcular la solución a los subproblemas.

El mismo problema usando Top-down tendría la siguiente estructura:

FUNC Fibonacci (↓n: NATURAL, ↨tabla: ARRAY [0..n] DE NATURAL): NATURAL

VARIABLES

i: NATURAL

INICIO

SI n <= 1 ENTONCES

devolver 1

FINSI

SI tabla[n-1] = -1 ENTONCES

tabla[n-1] ← Fibonacci(n-1, tabla)

FINSI

SI tabla[n-2] = -1 ENTONCES

tabla[n-2] ← Fibonacci(n-2, tabla)

FINSI

tabla[n] ← tabla[n-1] + tabla[n-2]

devolver tabla[n]

FIN

Suponemos que la tabla se introduce por primera vez correctamente inicializada, con todas las posiciones con un valor inválido, como por ejemplo -1, que se distingue por no ser uno de los valores que computa la función.

Con programación dinámica

Operación 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]

Métodos ascendentes y descendentes

Métodos descendentes (divide y vencerás)

– Empezar con el problema original y descomponer recursivamente en problemas de menor tamaño.

– Partiendo del problema grande, descendemos hacia problemas más sencillos.

• Métodos ascendentes (programación dinámica)

– 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.

• Algoritmo de Floyd.

Aplicación de la fórmula:

– Empezar por el problema pequeño: k = 0

– Avanzar hacia problemas más grandes: k = 1, 2, 3, ...

– ¿Cómo se garantiza que un algoritmo de programación dinámica obtiene la solución correcta?

• Una descomposición es correcta si cumple el
Principio de optimalidad de Bellman:

La solución óptima de un problema se obtiene combinando soluciones óptimas de subproblemas

O bien: cualquier subsecuencia de una secuencia óptima debe ser, a su vez, una secuencia óptima.

Ejemplo. Si el camino mínimo de A a B pasa por C, entonces los trozos de camino de A a C, y de C a B deben ser también mínimos.

Nota: el principio no siempre es aplicable.

Contraejemplo. Si el camino simple más largo de A a B pasa por C, los trozos de A a C y de C a B no tienen por qué ser soluciones óptimas.

Pasos para aplicar programación dinámica:

1)Obtener una descomposición recurrente del problema:

- Ecuación recurrente.

- Casos base.

2) Definir la estrategia de aplicación de la fórmula:

- Tablas utilizadas por el algoritmo.

- Orden y forma de rellenarlas.

3) Especificar cómo se recompone la solución final a partir de los valores de las tablas.

• Punto clave: obtener la descomposición recurrente.

• Requiere mucha “creatividad”...

Bibliografia:

*Enciclopecia Autodidactica Interactiva Oceano tomo 3