¡Divide y Vencerás la Programación Dinámica!

Cuando se empieza a competir en los maratones de programación, los que tienen más experiencia pueden llegar a intimidarnos un poco cuando discuten la solución de un problema. Mencionan algoritmos, técnicas y librerías de las que no tenemos ni idea y a veces se no hace difícil seguir la conversación. Personalmente, me intrigaba mucho cuando decían que tal o cual problema era una Programación Dinámica. En aquel momento, decidí investigar un poco por mi cuenta e intenté resolver algunos problemas relacionados (principalmente en SPOJ). Una de las referencias que más me ayudó fue el tutorial que tiene Topcoder sobre el tema. Sin embargo, más que ofrecerles otro tutorial completo, lo que quisiera a continuación es nada más que mencionarles, a grandes rasgos, de que se trata la programación dinámica y como podemos reconocer un problema de ese estilo.

Sin embargo, antes de empezar a discutir el tema, quisiera hablarles un poco sobre una técnica de resolución de problemas conocida como Divide y Vencerás. Esta técnica se basa en tomar un problema, dividirlo en varios problemas más pequeños (similares al original), resolver cada uno de esos subproblemas y luego unirlos de cierta forma tal que resuelva el problema original. Por ejemplo, veamos el algoritmo Mergesort. La intención es ordenar un arreglo y Mergesort logra este objetivo partiendo el arreglo a la mitad, ordenando cada una de estas mitades y luego uniendo las mitades ya ordenadas nuevamente en un solo arreglo (tal que este último continúe ordenado). Así para ordenar un arreglo, Mergesort solo necesita saber como ordenar arreglos que son de la mitad del tamaño del original. (Que es un problema similar, pero más pequeño) y luego saber como unirlos haciendo que el arreglo final resulte de igual forma ordenado.


Ahora, si esos subproblemas que acabamos de construir los mandamos a ordenar con el mismo Mergesort, tendremos un algoritmo recursivo. Éste partirá siempre el arreglo que debe ordenar a la mitad, luego ordenará cada mitad por separado y por último volverá a unir ambas partes. Sin embargo, como cada subproblema que generamos es más pequeño que el original, si continuamos haciendo esto, eventualmente llegaremos a llamar a Mergesort con un arreglo que tiene un solo elemento. Es imposible partir este arreglo de un solo elemento por la mitad. ¿Entonces que hacemos? ... La respuesta es simplemente devolver el mismo arreglo, ya que un arreglo de un solo elemento está inmediatamente ordenado. A este tipo de casos excepcionales se les conoce como caso base de la recursión y son necesarios siempre que se esté implementando un algoritmo recursivo.

Como pudimos ver, Mergesort es un ejemplo importante de la técnica de Divide y Vencerás, sin embargo no es el único. Hay muchos problemas que se pueden plantear de esta forma, dividiendo el problema original uno o más subproblemas y tratando luego cada uno de ellos por separado. Un momento... ¿Uno o más? ¿Puede dividirse en un solo subproblema? ... ¡La respuesta es que si! Y como ejemplo podríamos analizar el algoritmo de Búsqueda Binaria. Esto queda de ejercicio para el lector.

Pero este es un blog sobre maratones de programación, así que intentemos resolver un problema real de competencia. En esta ocasión, intentaremos resolver el problema PIGBANK de SPOJ.


Analicemos lo que nos están pidiendo. Nos dan un conjunto posible de monedas que tienen su propio peso y valor. Nos dan también un peso total que debemos cubrir exactamente con cualquier cantidad de las monedas disponibles (Este peso es la resta del peso de la alcancía llena y la alcancía vacía, F - E). Ahora bien, lo que queremos es minimizar el valor total posible. Crearemos entonces una función valmin (Valor mínimo), tal que:

valmin(W): El valor mínimo que se puede lograr, ocupando exactamente W de peso, utilizando cualquier cantidad de monedas posible.

Ahora, veamos que pasa si asumimos que una moneda m se encuentra dentro de la alcancía. Esto aseguraría que el valor mínimo que buscamos es por lo menos el valor de m. A este valor deberíamos sumarle luego el nuevo valor mínimo que es posible con el peso original menos el peso de la moneda m. Entonces, nuevamente estando seguros de que la moneda m se encuentra en la alcancía, tendríamos que se cumple la siguiente ecuación:

valmin(W) = costo de m + valmin(W - peso de m)

Sin embargo, no sabemos realmente que monedas se encuentran en la alcancía. Lo que podemos entonces es intentar tomar la moneda que mas nos convenga. ¿Y cual sería tal moneda? Dado que queremos minimizar, la mejor moneda es la que haga que la suma en la ecuación anterior sea la más pequeña posible.

valmin(W) = min i : 0 <= i < numero de monedas : costo de i + valmin(W - peso de i)

Conseguimos entonces una función recursiva para calcular el valor mínimo que necesitamos, sin embargo falta aún algo. ¿Que pasa cuando W es cero? ¿Cual es entonces el valor mínimo posible? La respuesta es también cero, pues la única forma de llenar un peso nulo es sin utilizar monedas.

valmin(0) = 0

Ahora tenemos también un caso base para la recursión, sin embargo aún no hemos terminado de formular la solución. ¿Que pasaría si para un cierto peso W, no existiese ninguna moneda que tenga peso menor a W? Si esto sucediera, no habría forma de incluir una moneda en la solución y por lo tanto debe reportarse que alcanzar tal peso con las monedas disponibles es en realidad imposible. Pero valmin es una función. ¿Que valores le asignamos a estos casos imposibles? Debe ser un valor que sea automáticamente peor que todos los demás valores posibles. Solamente existe un psuedonúmero con esa propiedad: El infinito. Nótese que para hacer el código más fácil podemos permitir que los casos imposibles hagan su llamada recursiva valmin(W - peso de i), que estaría llamando a valmin entonces con un valor negativo.

valmin(W) = Infinito, para todo W < 0


Pero el infinito no existe realmente en la computadora, lo que debemos es escoger un valor que sea lo suficientemente grande como para que se comporte de la misma forma. El primer valor que uno podría pensar es el máximo entero (2^31 - 1). Sin embargo, este valor tiene un problema. Si en una llamada recursiva valmin(W - peso de i) el resultado es (2^31 - 1), al sumarle el costo de i estaríamos incurriendo en un overflow, posiblemente resultando la suma en algún número negativo que haría que nuestro programa no se comporte como esperamos. Detalles como éste muchas veces hacen fallar a un programa que estaría correcto de haber escogido el infinito con más cuidado. Debemos buscar entonces un infinito que nos asegure que no haya overflow. Para eso analicemos el enunciado. Debemos asegurar que: costo de i + valmin(W - peso de i) no de overflow.

costo de i + valmin(W - peso de i) <= 2^31 - 1

El mayor valor posible para costo de i es 50000, por lo que tenemos lo siguiente:

50000 + valmin(W - peso de i) <= 2^31 - 1

Esto quiere decir que cualquier valor de infinito que sea menor que (2^31-1 - 50000) es un valor aceptable. Particularmente el valor 10^9 cumple con esa característica. ¿Será 10^9 lo suficientemente grande como para ser infinito? Veamos el caso extremo, que solo tengamos monedas de valor 50000 y peso 1, y además además queramos llenar una alcancía de peso 9999 (que es la máxima resta posible entre F y E). El menor y único valor posible en este caso sería 50000 * 9999 = 499950000 que es menor que 10^9.

Muy bien, ya tenemos todo lo que nos hace falta, solamente queda transcribir lo que hemos pensado a algún lenguaje de programación y enviarlo a SPOJ para que sea juzgado. Les recomiendo a los lectores que intenten hacer su propia implementación, sin embargo les dejó este enlace con una implementación propia de todo lo que se ha discutido hasta ahora.

Una vez enviemos el problema a SPOJ, nos daremos cuenta de que nuestro algoritmo es demasiado lento y el juez nos reportará un Time Limit Exceeded. ¿Por que está ocurriendo esto? Supongamos que hay dos monedas m1 y m2 que con seguridad están en la alcancía. Como estamos minimizando, la función valmin debe recorrer todas las monedas posibles para decidir cual es la mejor. Por lo tanto, valmin(W) llamará tanto a valmin(W - peso de m1) como a valmin(W - peso de m2). Ahora, dentro de la primera llamada recursiva, se intentará también en algún momento descontar la moneda m2, lo que resultaría en una llamada a valmin((W - peso de m1) - peso de m2). Por su parte, la segunda llamada recursiva eventualmente intentará descontar la moneda m1, lo que resultaría en una llamada a valmin((W - peso de m2) - peso de m1). Notemos que estas llamadas del segundo nivel de la recursión son en realidad la misma. ¡Y la estamos calculando dos veces! Imaginen entonces como sería con tres monedas, cuatro monedas, etc. Estamos recalculando muchas veces, muchas llamadas distintas a valmin. Esto hace que nuestro programa corra demasiado lento (de hecho, tomará un tiempo de ejecución exponencial con respecto al peso original de la alcancía y a la cantidad de monedas disponibles. De la razón de esto hablaré en alguna otra ocasión).


¿Como podemos evitarlo? Bueno, podríamos tener un arreglo que esté afuera de la función y que nos sirva para recordar que llamadas se han hecho hasta el momento. Esto es, cada vez que hagamos una llamada a valmin(W) guardaremos en ese arreglo que hemos ya calculado valmin para W y el valor que nos haya resultado. Como en ese arreglo deben caber todos los W posibles, debe tener al menos tamaño 10000 que es la cota superior para el mayor peso posible. Ahora, solo guardaremos este valor para el caso recursivo, no hace falta memorizarlo para el caso baso o el caso imposible, ya que estos son muy rápidos de calcular.

¿Como saber si ya hemos calculado valmin para algún W particular? Podríamos colocarle a la posición W del arreglo un valor imposible (como -1). Entonces, al inicio del calculo todas las posiciones del arreglo tendrían -1 y al transcurrir la ejecución, solo las que aún tengan -1 serán las que necesitaremos calcular. Realicemos entonces ese cambio a nuestro programa. (Nuevamente les aconsejo que implementen su propia solución, sin embargo pueden encontrar una implementación propia en este enlace. Si bien pudiera implementarse esta misma solución en Java, la razón por la que he escogido C++ pueden entontrarla aquí.)

Lo volvemos a mandar al juez de SPOJ y si hicimos todo bien, tendremos un problema aceptado. Lo único que hicimos fue recordar que cosas ya habíamos calculado y mejoramos muchísimo el tiempo de ejecución de nuestro programa. A eso que hicimos, de recordar lo calculado, es a lo que se conoce como Programación Dinámica.

Ahora bien, este problema que acabamos de resolver es muy similar a un problema clásico conocido como El Problema de la Mochila. Es buena idea investigar y saber resolver estos problemas clásicos, ya que al hallar la relación con el problema que queremos resolver podemos utilizar la misma estrategia que utilizan estos últimos. Wikipedia tiene una buena variedad de problemas clásicos de programación dinámica que vale la pena revisar.

¿Que sigue ahora? Practicar con otros problemas para terminar de ver como se puede dividir y vencer un problema, así como notar si las llamadas se repiten y luego si puediesen memorizarse. ¿Como reconocer un problema de programación dinámica? Casi siempre se querrá minimizar o maximizar una función y el tamaño de la entrada será muy grande como para intentar resolverlo por Fuerza bruta (Por ejemplo, la versión Divide y Vencerás sin memorización), pero lo suficientemente pequeños como para caber en la memoria de una máquina promedio (Aproximadamente hasta 10^7 enteros). Si la entrada es demasiado grande, posiblemente el problema se resuelva con un algoritmo ambicioso, una programación dinámica que ahorre memoria o una búsqueda binaria, todos tópicos que se cubrirán más adelante en el blog.

Como tarea les dejo que resuelvan el problema MIXTURES, y que luego vean la relación que guarda este último con el problema clásico de programación dinámica conocido como Multiplicación Encadenada de Matrices.

Bueno, espero les haya servido esta pequeña explicación de lo que se trata la Programación Dinámica. Cualquier comentario o sugerencia es como siempre más que bienvenido. ¡Muchísimas gracias por leer! Hasta la próxima.