Honestamente, se siente bastante aburrido. La parte más emocionante es determinar si un problema es realmente un problema de programación dinámica o si se puede resolver con programación dinámica. La solución de abajo hacia arriba suele ser bastante sencilla una vez que puede enmarcar la pregunta dentro de un marco de “programación dinámica”. Pero primero tenía que ser bueno en la programación dinámica. Eso no fue fácil.
Los problemas de programación dinámica fueron los más difíciles de resolver. Le pregunté a mis colegas por sugerencias y consejos, y en lugar de poder explicar las técnicas o conceptos relacionados con las estrategias de programación dinámica, me dirigieron a los problemas que “hicieron clic” para ellos. Esto no me ayudó.
No fue hasta que encontré el problema que “hizo clic” para mí y descubrí cómo aplicar los mismos principios a otro problema que realmente lo entendí. Ahora, cuando puedo identificar un problema como un problema de programación dinámica, son muy fáciles.
- Cómo averiguar si existen dos elementos en una matriz ordenada cuya suma es igual a algún número predefinido
- ¿Cuál es la mejor manera de implementar un iterador para un BST?
- ¿Cómo determinan los algoritmos de creación de mercado qué tan agresivamente deberían salir de las posiciones?
- ¿Cuál es el mejor algoritmo de clasificación para alfabetizar físicamente mi colección de libros?
- ¿Cuáles son algunas optimizaciones comunes que los clientes de GPS como Google Maps usan además de los algoritmos elementales de ruta más corta como la búsqueda A *?
Por lo tanto, esto es completamente no solicitado, y probablemente no sea apropiado en esta respuesta, pero quiero que obtenga una programación dinámica, porque realmente cualquier persona con la motivación puede obtenerla . Voy a intentar, como, imagino, muchos antes que yo, explicar la programación dinámica paso a paso desde la identificación hasta la construcción de una solución y, con suerte, te acercaré un poco más a ese momento en que todo “hace clic”.
Esto va a ser largo
Mi problema de “clic” fue el “problema de la barra” que encontré en Cormen (Introducción a los algoritmos).
Se puede vender una barra de metal de acuerdo con la longitud L a un precio P en
precios (una matriz con índice de longitud y precio acordado como el
valor). Una varilla dada se puede cortar tantas veces como sea necesario en
longitudes discretas (enteros). Dada una varilla de longitud L, determine el
El precio más alto que podemos vender es la barra haciendo los cortes apropiados.
Entonces, la parte más difícil de un problema de programación dinámica es casi siempre identificar que es, de hecho, un problema de programación dinámica. Hay algunas cosas que deberían informarle:
- Optimización: los problemas de programación dinámica a menudo son preguntas de optimización, y el aviso solicita una solución óptima (valores máximos, valores mínimos, mejores precios, etc.) entre todas las soluciones posibles.
- Subproblemas superpuestos: la programación dinámica nos permite optimizar las soluciones de problemas que son el resultado de subproblemas superpuestos. ¿Qué significa esto? En las soluciones de divide y vencerás, dividimos el problema en subproblemas discretos y no superpuestos ; dividimos una matriz por la mitad y solo miramos la mitad. Con problemas de programación dinámica, resolvemos un subproblema que involucra uno o dos elementos, y usamos esa solución para el siguiente subproblema que involucra dos o tres elementos. Esto se volverá un poco más lúcido cuando me meta en el problema en sí, a continuación.
- Todas / La mayoría de las soluciones posibles importan: esta es una especie de repetición de 1. La idea es que solo podemos ver una o dos entradas. En la mayoría de los casos, necesitamos calcular todas las soluciones para encontrar la mejor solución. Por ejemplo, en un problema clásico de programación dinámica, calcular números de Fibonacci, para determinar el enésimo número de Fibonacci, necesitamos calcular todos los números de Fibonacci a partir de 1 .. n-1 .
- Se siente codicioso: la programación dinámica es una combinación de estrategias de fuerza bruta y codicioso. Estamos analizando todas las soluciones posibles, haciendo un seguimiento de las mejores soluciones a medida que avanzamos y usándolas para calcular las mejores soluciones futuras.
El problema de la barra
Bien, estos consejos deberían ayudarnos a determinar si este problema es una programación dinámica. Sabemos que tenemos una lista de precios según la longitud, y sabemos que tenemos una barra de cierta longitud discreta. Sabemos que podemos hacer tantos cortes discretos como queramos, por lo que no es demasiado estiramiento, tendremos que probar muchas combinaciones de longitudes de varilla para determinar qué combinación es más rentable. Aquí es donde debes dejar de pensar tanto en las combinaciones . Mi instinto siempre fue saltar de inmediato a descubrir cómo calcular todas esas combinaciones y nunca llega a la solución que necesita.
En cambio, debemos darnos cuenta de que una solución óptima a este problema es el resultado de comparar una serie de subproblemas (todas esas combinaciones). Ahora deberíamos pensar si estos subproblemas se superponen o no. Entonces, en términos concretos, ¿necesitaré alguno de estos subproblemas para resolver otros subproblemas? ¿El precio de una barra de longitud 2 me ayudará a resolver una barra de longitud 5? ¿Qué tal de longitud 4? ¿Qué tal la longitud 6? Dado que todas estas posibilidades más grandes podrían cortarse en longitudes de 2 para aumentar las ganancias, parece que la solución para una varilla de longitud 2 podría ser algo que queremos usar en el futuro.
Entonces, ahora sabemos que estamos buscando una solución óptima entre muchas soluciones (pista 1.), sabemos que este problema se compone de subproblemas superpuestos (2), y que al menos algunos de estos problemas serán importantes para calcular La solución óptima (3). Puede que no sea un tramo demasiado grande para ver cómo se aplica la pista 4. De todos modos, tenemos suficiente evidencia para concluir que la programación dinámica nos ayudará.
De abajo hacia arriba!
Veremos lo que se llama el enfoque ascendente, porque creo que es un enfoque más flexible y (cuando se explica adecuadamente) más educativo para la programación dinámica.
** **
Como referencia, una solución a menudo más fácil de implementar es una solución recursiva que utiliza la memorización para almacenar soluciones a subproblemas recurrentes. Estas se llaman soluciones de arriba hacia abajo.
A pesar de la facilidad de implementación, encuentro que las soluciones de arriba hacia abajo son más difíciles de implementar para varias soluciones, mientras que las soluciones de abajo hacia arriba son bastante flexibles.
Además, las soluciones ascendentes son casi siempre más fáciles de analizar en términos de complejidad de tiempo y espacio, y siempre son prácticamente óptimas debido a la sobrecarga que implican las pilas recursivas.
** **
Dada una varilla de longitud L, ahora sabemos que primero necesitaremos encontrar todas las soluciones de 1 a L -1. Construyamos nuestro esqueleto (usaré python aquí). Sabemos que tomaremos rod_length y precios como entradas iniciales:
def best_rod_profit (rod_length, precios):
Antes de comenzar a ver los valores entre 1 y L, pensemos en la solución más fácil que se nos ocurra. ¿Qué pasa si L = 0? El sentido común dictaría que una varilla de longitud 0 no valdría nada. Supongamos que, por el bien de este ejemplo, los precios [0] = 0 (de lo contrario, nuestro beneficio sería efectivamente Infinito).
Vamos a crear un hash de referencia (o diccionario, en términos de Python) para almacenar los mejores valores incrementales a medida que avanzamos. Entonces, para una varilla de longitud L, queremos poder encontrar la mejor ganancia accediendo a algo como best_profits [L]. Como se indicó anteriormente, vamos a inicializar esto con un par clave-valor de 0: 0.
def best_rod_profit (rod_length, precios):
best_profits = {
0: 0
}
Lo siguiente que queremos hacer, como en una estrategia de Greedy, es comenzar desde una longitud de 1 e incrementar en uno. ¡Eso es todo en lo que vamos a pensar por ahora! Todo lo que sabemos en este momento es que necesitamos las soluciones de 1 – L-1 para construir una solución a L. Llegaremos a lo que realmente haremos para esos valores en un momento, por ahora, configuremos nuestro incremento:
def best_rod_profit (rod_length, precios):
best_profits = {
0: 0
}
para longitud en rango (1, len (rod_length) + 1):
Bien, entonces nos estamos moviendo de 1 a L (recuerde que los rangos de Python son exclusivos, de ahí el + 1).
Ahora, ¿qué vamos a hacer con estas longitudes? Bueno, vamos a descubrir la mejor ganancia posible que podemos obtener de una longitud determinada.
Es bastante fácil cuando L = 1. No podemos dividirlo más, así que solo podemos ver los precios [1]. Ese es nuestro mejor valor para uno. Puede ser mejor haber configurado esto dentro de nuestras mejores ganancias al comienzo de este problema, pero es útil verlo dentro de la iteración para fines de demostración.
Entonces, eso se ve así:
def best_rod_profit (rod_length, precios):
best_profits = {
0: 0
}
para longitud en rango (1, len (rod_length) + 1):
best_profits [longitud] = precios [longitud]
Obviamente, esto no funciona para L = 2 en muchos casos. Si, por ejemplo, nuestra matriz de precios se configura como:
precios = [0, 2, 2]
Es mejor para nosotros cortar una barra de L = 2 en dos barras de longitud 1, ya que eso nos daría una mayor ganancia (4) que preservar la longitud de la barra en L = 2 (2).
Entonces, ¿cómo debemos calcular esto?
Aquí es donde la magia de la programación dinámica comienza a manifestarse. En este punto de la iteración, nuestro valor iterativo, longitud, es 2. Para encontrar el mejor_profito para 2, necesitamos conocer las mejores ganancias de todos los subproblemas posibles. Entonces, imagine que comenzamos con un solo corte de la varilla y distinguimos entre el lado izquierdo y el lado derecho. Ahora digamos que no vamos a cortar el lado izquierdo. Sin embargo, echemos un vistazo al lado derecho y busquemos la mejor_profit que podamos obtener de eso.
Algo como:
precios [izquierda] + mejores ganancias [derecha]
¿Como funciona esto? ¿Cómo es esto posible? ¿Cómo podemos estar absolutamente seguros de que ya tenemos el valor de best_profits [correcto]? Bueno, dado que vamos a hacer esto dentro de nuestra iteración, sabemos que para cualquier valor de longitud si es correcto, derecho debe ser menor o igual que la longitud. La única parte propensa a errores de esto es ese último bit; si derecho es igual a longitud. Esto significa que debemos asegurarnos de que el derecho solo alcance un máximo de longitud: 1. Esto tiene sentido, porque best_profits [right] es la respuesta que estamos buscando para este subproblema.
Bien, entonces, ¿cómo determinamos los distintos valores de izquierda y derecha? Bueno, vamos a la izquierda como toda la longitud, y cortaremos piezas de longitud creciente hasta la longitud mínima de 1 remanente. De esta forma, verificaremos el valor completo, los precios [2] (en el caso de la longitud = 2) y los valores parciales posteriores, solo los precios [1] en este caso.
Algo como esto:
para derecho en rango (longitud):
izquierda = longitud – derecha
Entonces, la derecha comienza en 0, dejando a la izquierda en longitud y aumenta hasta la longitud – 1, donde izquierda es 1.
Entonces, esto es lo que tenemos hasta ahora:
def best_rod_profit (rod_length, precios):
best_profits = {
0: 0
}
para longitud en rango (1, len (rod_length) + 1):
para derecho en rango (longitud):
izquierda = longitud – derecha
Bien, ahora necesitamos comparar todos estos valores de diferentes longitudes izquierda y derecha y encontrar el más rentable. ¿Cómo? Vamos a utilizar un enfoque de avaricia. Para un enfoque Greedy dado, revisamos cada combinación de valores en una sola pasada, haciendo un seguimiento de los mejores actuales. Para este problema, vamos a inicializar current_best en 0, pero esto puede no tener sentido para todos los problemas de programación dinámica.
def best_rod_profit (rod_length, precios):
best_profits = {
0: 0
}
para longitud en rango (1, len (rod_length) + 1):
current_best = 0
para derecho en rango (longitud):
izquierda = longitud – derecha
current_profit = precios [izquierda] + best_profits [derecha]
current_best = max (current_best, current_profit)
Ok, genial! Eso es correcto? Ahora podemos asignar el current_best a la clave adecuada de best_profits, ¿verdad? Incorrecto. Necesitamos hacer una cosa más que no siempre parece intuitiva. Necesitamos comparar el current_best con el valor de best_profits de la longitud anterior.
¿Por qué? Es importante tener en cuenta que las longitudes de varilla posteriores pueden no ser más rentables que las longitudes de varilla anteriores. ¿Qué pasa si nuestro current_best para length = 5 es menor que para length = 2 (piense en valores negativos y 0 aquí)? En ese caso, es esencialmente mejor tirar la longitud extra y pretender que solo tienes la barra más pequeña.
Si bien esto no parece realista, es una consideración importante para la gama más amplia de problemas de programación dinámica.
Entonces, terminamos con:
def best_rod_profit (rod_length, precios):
best_profits = {
0: 0
}
para longitud en rango (1, len (rod_length) + 1):
current_best = 0
para derecho en rango (longitud):
izquierda = longitud – derecha
current_profit = precios [izquierda] + best_profits [derecha]
current_best = max (current_best, current_profit)
best_profits = max (current_best, best_profits [longitud – 1])
return best_profits [rod_length]
¡Y eso es!
entonces, ¿qué hicimos? Para cada longitud posible de varilla de 1 a rod_length, encontramos el mejor beneficio usando el enfoque codicioso. Almacenamos ese valor en un Hash (o diccionario en este caso) y lo referenciamos en futuros subproblemas.
Una vez finalizado, simplemente devolvemos el valor de best_profits de la longitud máxima para la que resolvimos: rod_length.
Entonces, ¿cómo podemos aplicar lo que hemos aprendido y aplicarlo a otros problemas? Lo que hace que esta implementación sea realmente específica para este problema son las líneas 9 y 10. El uso de una barra de longitudes discretas nos permite visualizar los valores izquierdo y derecho de forma lineal. ¿Qué pasa con otro problema de programación dinámica popular, el problema “Hacer cambio”, en el que necesitamos encontrar el número mínimo de monedas para hacer el cambio con un conjunto de monedas proporcionado?
En ese caso, en lugar de iterar hasta la longitud actual, haremos una sublista de todas las monedas menos que el valor actual. Como mantuvimos “el lado izquierdo constante” e incrementamos el derecho, mantendremos una moneda constante y buscaremos el mejor cambio para el resto:
def make_change (valor, monedas):
best_change = {
0: 0
}
para cambio de rango (1, valor + 1):
current_best = change
curent_coins = []
para moneda en monedas:
si moneda <= cambio:
current_coins.append (moneda)
para monedas en current_coins:
current_coins = 1 + best_change [cambio – moneda]
current_best = min (current_coins, current_best)
best_change = min (current_best, change)
return best_change [valor]
** Asumimos que hay una moneda de 1 valor. Tendríamos que modificar nuestra respuesta, de lo contrario. ** **
Entonces, ¿qué hay de diferente aquí? Recuerde, en lugar de ganancias máximas, estamos buscando un número mínimo de monedas. Entonces, el valor mínimo establecido en la línea 7 es el peor valor, la cantidad de monedas que usaríamos si solo las monedas de valor = 1.
En lugar de simplemente restar valores de una longitud y mantener constante un lado, recolectamos todas las monedas posibles que podríamos usar y mantenemos cada una “constante” comprobando el mejor cambio para el valor restante si utilizamos la moneda que mantenemos “constante”.
Realmente, eso es lo único diferente. Simplemente estamos reuniendo nuestros valores para una solución codiciosa de una manera específica para el problema. Todo lo demás permanece igual o similar.
Conclusión
Uf. Trate de encontrar otros problemas de programación dinámica y realmente trabaje en ellos hasta que tenga el momento de “clic”. Intente practicar identificando problemas de programación dinámica. Realmente trabaje en cada problema tratando de construir su comprensión. Una vez que trabaje con ellos lo suficiente, comenzará a ver surgir patrones.
Pruebe el problema de la mochila sin límites (casi exactamente el mismo que el problema de make_change), luego trabaje hasta el problema de la mochila 0/1 y vea cómo difieren sus soluciones.
*****
Espero que esto ayude incluso un poco. Una vez que obtiene este tipo de problemas, parece que tiene una subsección completa de problemas de algoritmos dominados. ¡Y estoy seguro de que con la motivación adecuada cualquiera puede hacerlo!
Avíseme si hay alguna parte de esto que no sea clara, verbal, técnica o de otra manera ininteligible.
También avíseme si mis soluciones tienen errores u otros problemas. Me gustaría asegurarme de que todo esto sea lo más claro posible, y tiendo a ser locuaz.
¡Buena suerte!
