Esta pregunta es un poco engañosa, porque supone que algunos problemas son “problemas de programación dinámica” y otros no. En teoría, podría usar la programación dinámica para resolver cualquier problema. La verdadera pregunta es si quieres o no.
La programación dinámica es una de las muchas herramientas algorítmicas que debería tener disponibles en su caja de herramientas algorítmicas. Desde mi experiencia personal, es la herramienta más útil para resolver problemas que están en el límite de ser manejables e intratables .
Los problemas manejables son aquellos que pueden resolverse con un algoritmo de tiempo polinómico. Los problemas intratables son aquellos que parecen resolverse solo con algoritmos que se ejecutan en tiempo de ejecución exponencial o peor. Por ejemplo, se cree que toda la clase de problemas NP-completos es intratable (aunque nadie puede probarlo).
- Cómo inicializar una matriz de cadenas en una clase
- ¿Qué nuevos algoritmos ha creado Google?
- ¿Por qué todavía no tenemos matrimonios estables cuando el problema del matrimonio estable se resolvió en 1962?
- ¿Cuál es la mejor manera de implementar un iterador para un BST?
- ¿Cuál es la complejidad temporal del algoritmo babilónico para encontrar la raíz cuadrada?
Lo primero que debe hacer cuando se le presenta un problema con el que no está familiarizado es pensar primero cuál sería la solución de fuerza bruta. Por lo general, la solución de fuerza bruta tendrá un tiempo de ejecución horrible, probablemente un tiempo de ejecución factorial.
La siguiente pregunta que debe hacerse es si el problema es obviamente manejable (es decir, si existe una solución obviamente correcta que sea mucho más eficiente que la fuerza bruta).
Como un ejemplo trivial, considere ordenar. La solución de la fuerza bruta sería considerar todos los ordenamientos posibles y elegir el que está en el orden correcto. Este es tiempo factorial y un algoritmo muy muy horrible. Pero hay un algoritmo obvio que es mucho más eficiente que eso, Selección Ordenar (es decir, encontrar el elemento más pequeño, luego el siguiente más pequeño, etc.) Por lo tanto, la clasificación es obviamente manejable. ¿Es Selection Sort el algoritmo más eficiente? No, pero dado que el problema obviamente ya es muy manejable, no recurriría a DP para encontrar un algoritmo mejor.
Ahora, consideremos algunos problemas como el Vendedor ambulante, la Mochila y la Subsecuencia creciente más larga, jugar al Tic-Tac-Toe, etc. Las soluciones de fuerza bruta a estos problemas deberían ser tan obvias como para la clasificación, y nuevamente son un tiempo factorial realmente malo algoritmos La diferencia es que con estos problemas, después de pensar en ellos por un período de tiempo, aún no es obvio que no son intratables. Parece que hay una explosión combinatoria natural en el problema que es difícil de evitar.
Aquí es cuando es hora de sacar la Programación Dinámica de su caja de herramientas, antes de darse por vencido y asumir que el algoritmo de fuerza bruta es el mejor. Resulta que en cada uno de los problemas que mencioné anteriormente, DP le dará una mejor solución que la fuerza bruta. Aunque, eso no siempre significa que el problema sea manejable. Por ejemplo, para TSP, aunque la programación dinámica se puede utilizar para reducir el tiempo de ejecución de factorial a exponencial, todavía es intratable (y se presume que siempre lo será, ya que TSP es NP-Complete). Para Knapsack, DP le ofrece un mejor algoritmo, pero solo es un pseudopolinomio.
El uso de la programación dinámica tampoco garantiza que obtendrá el algoritmo con el mejor tiempo de ejecución. Por ejemplo, usando DP, no es difícil obtener un tiempo de ejecución de O (n ^ 2) para el problema de Subsecuencia de Mayor Incremento, pero obtener el algoritmo de O (n log n) requiere un montón de trucos adicionales. Del mismo modo, por ejemplo, el problema de la ruta más corta, podría usar DP para obtener una solución razonable, pero no sería tan bueno como simplemente usar Dijkstra.
Además, el simple hecho de saber que debe resolver un problema con DP no le dice realmente cómo hacerlo. A menudo, es posible que deba reformular el problema de varias maneras antes de ver cómo DP le dará una buena solución. Por lo tanto, realmente necesita estudiar un montón de problemas que se resuelven utilizando la Programación dinámica para tener una idea de ellos, y pensar en diferentes formas en que estos problemas podrían reformularse. Los problemas de tipo mochila pueden disfrazarse de miles de millones de maneras diferentes.
Algo más a considerar es que lo bueno de los algoritmos DP es que, por lo general, su prueba de corrección es evidente. Otras estrategias algorítmicas son a menudo mucho más difíciles de probar correctas, y por lo tanto más propensas a errores. Por ejemplo, los algoritmos codiciosos pueden parecer conceptualmente más simples y, por lo general, se ejecutan más rápido, pero es mucho más difícil demostrar que son correctos porque generalmente requieren hacer muchas suposiciones implícitas sobre la estructura de su entrada. Y la exactitud de esos supuestos implícitos es la diferencia entre un algoritmo que solo funciona algunas veces y uno que funciona todo el tiempo.
