Introducción A La Programación Dinámica

Hace pocos días, los muchachos de Bátiz y Martín me dieron una clase de programación dinámica. Los pasos para dominar esta técnica son:

1. Tener Un Problema Que Se Resuelva Con Programación Dinámica

Creo que un borrego necesita recorrer un tablero de Y filas y X columnas, empieza en la casilla superior izquierda y termina en la casilla inferior derecha. Cada casilla tiene un costo en vitaminas y el borrego quiere gastar la menor cantidad de vitaminas posibles.


Por cierto, el borrego sólo puede caminar para abajo y para la derecha.


Ajá! Un mínimo! Dicen que si el problema te pide un mínimo o un máximo, entonces huele a programación dinámica.

Una posible entrada para este problema sería:

2 3
1 4 2
2 3 6

2. Dibujar El Árbol De Búsqueda

Como verán, el árbol tiene un crecimiento exponencial en potencias de dos (2ⁿ).

Algunos nodos como el y=1,x=1 se calculan varias veces. Más adelante podemos utilizar memorización para ahorrar cálculos.

3. Versión Backtracking

Esa búsqueda tiene una implementación con Backtracking muy sencilla.

#include <iostream>
#include <climits>

#define Y_MAX 1111
#define X_MAX 1111

using namespace std;

int Y, X;
int tablero[Y_MAX][X_MAX];

int minimo (int a, int b) {
	return (a < b ? a :  b);
}

int f (int y, int x) {
	// destino final
	if (y == Y - 1 && x == X -1)
		return tablero[y][x];
	// fuera del tablero
	if (x >= X || y >= Y)
		return INT_MAX;
	// calcular el mejor camino desde aquí
	return minimo(f(y + 1, x), f(y, x + 1)) + tablero[y][x];	
}

int main () {
	cin >> Y;
	cin >> X;
	
	// entrada
	for (int y = 0; y < Y; y++) {
		for (int x = 0; x < X; x++) {
			cin >> tablero[y][x];
		}
	}
	
	// salida
	cout << f(0, 0) << endl;
}

4. Versión Backtracking Con Memorización

Guardar en memoria los valores ya calculados, evita calcular varias veces el mismo dato y mejora considerablemente el tiempo.

#include <iostream>
#include <climits>

#define Y_MAX 1111
#define X_MAX 1111

using namespace std;

int Y, X;
int tablero[Y_MAX][X_MAX];
int poda[Y_MAX][X_MAX];

int minimo(int a, int b) {
	return (a < b ? a :  b);
}

int f(int y, int x) {
	// destino final
	if (y == Y - 1 && x == X -1)
		return tablero[y][x];
	// fuera del tablero
	if (x >= X || y >= Y)
		return INT_MAX;
	if (poda[y][x] == 0)
		poda[y][x] = minimo(f(y + 1, x), f(y, x + 1)) + tablero[y][x];
	return 	poda[y][x];
}

int main () {
	cin >> Y;
	cin >> X;
	
	// entrada
	for (int y = 0; y < Y; y++) {
		for (int x = 0; x < X; x++) {
			cin >> tablero[y][x];
		}
	}
	
	// salida
	cout << f(0, 0) << endl;
}

5. Encontrar La Función De Programación Dinámica

Una implementación con Programación Dinámica será más eficiente. ¿Pero cómo se calculan los valores? Analizando el árbol, se ve que el valor de un nodo depende de los siguientes nodos.

Entonces, para llenar la tabla deberá de llenarse primero los niveles más avanzados. En este caso sería de abajo para arriba y de izquierda a derecha.

Cada condición del backtracking se debe analizar para ver si se incluyen en la versión dinámica o no. En este caso son los límites if (x >= X || y >= Y).

La importancia de la programación dinámica es eliminar la recursividad.

6. Versión Programación Dinámica

#include <iostream>
#include <climits>

#define Y_MAX 1111
#define X_MAX 1111

using namespace std;

int Y, X;
int tablero[Y_MAX][X_MAX];

int minimo(int a, int b) {
	return (a < b ? a :  b);
}

int main () {
	cin >> Y;
	cin >> X;
	
	// entrada	
	for (int y = 0; y < Y; y++) {
		for (int x = 0; x < X; x++) {
			cin >> tablero[y][x];
		}
	}
	
	// poner infinitos
	for (int y = 0; y < Y; y++) {
		tablero[y][X] = INT_MAX;
	}
	
	for (int x = 0; x < X; x++) {
		tablero[Y][x] = INT_MAX;
	}
	
	// poner ceros en casillas adyacentes a la casilla final
	tablero[Y-1][X] = 0;
	tablero[Y][X-1] = 0;
	
	// programación dinámica
	for (int y = Y - 1; y >= 0; y--) {
		for (int x = X - 1; x >= 0; x--) {
			tablero[y][x] += minimo(tablero[y + 1][x], tablero[y][x + 1]);
		}
	}
	
	// salida
	cout << tablero[0][0] << endl;
}

7. Prueba De Escritorio

Al finalizar la ejecución, el tablero en memoria debe terminar así:

8. Resultados Interesantes

Por último, analicemos los tiempos (en milisegundos) con cada versión y diferentes casos de prueba.

Caso De Prueba	Backtracking	Backtracking Con Memorización	Programación Dinámica
10x10	35	35	35
100x100	mucho	75	70
1000x1000	muchísimo	3895	3844