La mayoría de los problemas de DP se pueden dividir en dos tipos: problemas de optimización y problemas combinatorios. Los problemas de optimización requieren que elija una solución factible para que el valor de la función objetivo se minimice (o maximice). Los problemas combinatorios solicitan la cantidad de formas de hacer algo o la probabilidad de algún evento. Echemos un vistazo más de cerca a estos tipos de problemas.
Problema de optimización DP
El problema de optimización pide elegir la mejor solución posible de acuerdo con alguna función de objetivo. Tanto las monedas como los ejemplos de LCS son del tipo de optimización. La ecuación recurrente se parece a R [s] = min (F1 (R [i], R [j],…, R [k]), F2 (R [u], R [v],…, R [w] ), …, Fl (R [q], R [p], …, R [z])), donde R es la matriz de resultados DP. Simplemente hablando, el resultado se elige como el mejor = mínimo entre los varios casos candidatos. Para cada caso, el resultado se calcula a partir de los resultados de los estados DP anteriores. Por ejemplo, en el problema de las monedas, se consideran todos los últimos casos posibles de monedas. Cada uno de ellos produce un caso en la fórmula recurrente. El resultado para el estado es un mínimo entre todos estos casos. En el ejemplo de LCS hubo tres casos: primera palabra, última letra sin usar, segunda palabra, última letra sin usar y ambas palabras, última letra usada.
- ¿Qué calcularía los algoritmos pesados en matemáticas más rápido: FPGA o GPU?
- ¿Deep Blue fue un algoritmo o una IA o ambos?
- ¿Cómo puedo aleatorizar la matriz almacenada y luego usarla como entrada?
- ¿Cuáles son las aplicaciones de las estructuras de datos?
- El emparejamiento PvP "perfectamente justo" daría como resultado una tasa de ganancia esperada del 50% para todos. Eso puede sentirse muy bajo (sesgo de confirmación, rayas malas). Además de PvP asincrónico, ¿hay alguna manera de aumentar el WR percibido de todos mientras se mantiene justo el MM?
A menudo es útil llenar la matriz de resultados DP con valores neutros antes de calcular cualquier cosa. El valor neutral es un resultado que no afecta la respuesta del problema con seguridad. En caso de problema de minimización, el valor neutral es infinito positivo: dado que es mayor que cualquier número, todas las fórmulas recurrentes preferirían un caso con valor finito a un elemento tan neutral. En otras palabras, el estado con resultado de valor neutral puede considerarse como un estado imposible. Tenga en cuenta que para el problema de maximización, el infinito negativo es un elemento neutral.
Los estados DP a menudo se denominan subproblemas DP porque representan algún problema para los datos de entrada que es un subconjunto de la entrada del problema completo. Por ejemplo, en el caso de LCS, cada subproblema involucra dos prefijos arbitrarios de las dos palabras originales. El método DP se basa en la propiedad óptima de la subestructura: dada la solución óptima para todo el problema, sus soluciones parciales deben ser óptimas para los subproblemas. En el caso de las monedas, significa que si la solución para todo el problema con el peso total S es óptima y contiene monedas con peso w, entonces la solución sin monedas w también debe ser óptima para el subproblema con peso total (S – w).
La propiedad óptima de la subestructura es muy importante: si no se mantiene y la solución óptima tiene la subsolución que no es óptima, entonces se descartaría en algún lugar en el medio de DP al tomar el mínimo. A menudo, la solución DP resulta ser teóricamente incorrecta porque carece de la subestructura óptima. Por ejemplo, hay un clásico problema de vendedor ambulante. Deje que el dominio de estado DP sea (k, l) -> D, donde D es la longitud mínima de la ruta simple que atraviesa exactamente k ciudades, siendo 0-th city la primera y l-th city siendo la última. La propiedad de subestructura óptima en un DP de este tipo no se cumple: dado el recorrido más corto, su ruta secundaria con la última ciudad fija y el número total de ciudades no siempre es el más corto. Por lo tanto, el DP propuesto estaría equivocado de todos modos.
Problema DP combinatorio
El objetivo del problema de DP combinatorio es encontrar varias formas de hacer algo o la probabilidad de que ocurra el evento. A menudo, el número de formas puede ser grande y solo se requiere un módulo de recordatorio. La ecuación recurrente se parece a R [s] = F1 (R [i], R [j],…, R [k]) + F2 (R [u], R [v],…, R [w]) + … + Fl (R [q], R [p], …, R [z]). La única diferencia del caso de optimización es la suma en lugar del mínimo, y cambia mucho. La suma significa que las diferentes formas de los casos F1, F2, …, Fl comprenden todas las formas de estado (s).
El ejemplo del caso combinatorio es un problema de monedas modificadas: cuente la cantidad de formas de elegir monedas para que su peso total sea igual a S. El dominio de estado es el mismo: (P) -> k donde k es la cantidad de formas de elegir monedas para que su peso total sea exactamente P. Las ecuaciones recurrentes son solo un poco diferentes en problemas combinatorios.
/ * Ecuaciones recurrentes para DP:
{k [0] = 1;
{k [P] = sum_i (k [P-Wi]); (para Wi <= P)
* /
/ * Considere los datos de entrada: S = 11, n = 3, W = {1,3,5}
La tabla de resultados de DP es:
P = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11
—— + – + – + – + – + – + – + – + – + – + – + –
k = 1 | 1 | 1 | 2 | 3 | 5 | 8 | 12 | 19 | 30 | 47 | 74
* /
También hay un valor neutral para el problema combinatorio. Como el problema combinatorio usa la sumatoria, el elemento neutral es cero. Los resultados de DP en caso combinatorio generalmente representan varias formas de hacer algo, por lo que si el resultado es cero, entonces no hay forma de hacerlo. El valor del resultado neutral significa que el caso es imposible. Puede ser útil llenar la matriz de resultados DP con valores cero, aunque generalmente se hace automáticamente. En el caso de la combinatoria, es importante que se cuente cada forma posible y que no se cuente más de una vez. La segunda condición es a veces difícil de satisfacer.
