algorithm - software - programacion dinamica unam
¿En qué se diferencia la programación dinámica de los algoritmos codiciosos? (7)
La diferencia clave es que los algoritmos codiciosos componen soluciones "estáticamente" en el sentido de que cada opción local en la solución se puede finalizar sin necesidad de saber nada sobre las otras elecciones locales realizadas. Los algoritmos dinámicos, sin embargo, crean conjuntos de posibles soluciones a subproblemas y solo generan una única solución al problema global cuando se han considerado todos los subproblemas. La página de Wikipedia sobre algoritmos codiciosos lo explica bien:
La elección hecha por un algoritmo codicioso puede depender de las elecciones realizadas hasta el momento, pero no de las opciones futuras o de todas las soluciones al subproblema. Hace iterativamente una elección codiciosa tras otra, reduciendo cada problema dado en uno más pequeño. En otras palabras, un algoritmo codicioso nunca reconsidera sus elecciones. Esta es la diferencia principal de la programación dinámica, que es exhaustiva y está garantizada para encontrar la solución. Después de cada etapa, la programación dinámica toma decisiones basadas en todas las decisiones tomadas en la etapa previa, y puede reconsiderar el camino algorítmico de solución de la etapa anterior.
En el libro que estoy usando Introducción al Diseño y Análisis de Algoritmos , se dice que la programación dinámica se centra en el Principio de Optimización , "Una solución óptima para cualquier instancia de un problema de optimización se compone de soluciones óptimas para sus subinstancias".
Mientras que, la técnica codiciosa se enfoca en expandir soluciones parcialmente construidas hasta que llegue a una solución para un problema completo. Luego se dice que debe ser "la mejor elección local entre todas las opciones posibles disponibles en ese paso".
Como ambos implican optimalidad local, ¿no es uno un subconjunto del otro?
La diferencia entre DP y codicioso es que DP buscará el óptimo global en cada subproblema, pero codicioso solo buscará el óptimo local. Entonces, esto sobre este escenario:
Supongamos que estás escalando una montaña y quieres subir lo más alto posible. El camino en la montaña tiene varias ramas, y en cada intersección necesitas decidir qué rama tomar, que es el subproblema de este problema de escalada (el objetivo es el mismo, solo el punto de partida es diferente)
Para el algoritmo codicioso, siempre elegirá el que parezca más pronunciado. Esta es una decisión óptima local y no se garantiza que conduzca al mejor resultado
Para el DP, en cada intersección, ya debes saber la altitud más alta a la que te llevará cada rama (supongamos que tu orden de evaluación se invierte, también desde los puntos finales hasta el punto de partida), y elige la que tenga la mayor altitud. Esta decisión se basa en el óptimo global de los futuros subproblemas y allí será óptima a nivel mundial para este subproblema
La diferencia es que la programación dinámica requiere que recuerde la respuesta para los estados más pequeños, mientras que un algoritmo codicioso es local en el sentido de que toda la información necesaria se encuentra en el estado actual. Por supuesto, hay una intersección.
La programación dinámica es aplicable a problemas que exhiben las propiedades de:
- solapados de subproblemas, y
- subestructura óptima.
La subestructura óptima significa que puede resolver con avidez los subproblemas y combinar las soluciones para resolver el problema más grande. La diferencia entre la programación dinámica y los algoritmos codiciosos es que con la programación dinámica, hay subproblemas superpuestos, y esos subproblemas se resuelven mediante la memorización . "Memoization" es la técnica mediante la cual las soluciones a subproblemas se utilizan para resolver otros subproblemas más rápidamente.
Esta respuesta ha recibido algo de atención, así que daré algunos ejemplos.
Considere el problema "Hacer cambios con dólares, cinco centavos y centavos". Este es un problema codicioso. Exhibe subestructura óptima porque puede resolver por el número de dólares. Luego, resuelve por el número de monedas de cinco centavos. Entonces la cantidad de centavos. A continuación, puede combinar las soluciones a estos subproblemas de manera eficiente. En realidad, no presenta subproblemas superpuestos, ya que resolver cada subproblema no ayuda mucho con los demás (tal vez un poco).
Considere el problema "Números de Fibonnaci". Exhibe una subestructura óptima porque puedes resolver F (10) de F (9) y F (8) de manera eficiente (por adición). Estos subproblemas se superponen porque ambos comparten F (7). Si memoriza el resultado de F (7) cuando resuelve F (8), puede resolver F (9) más rápidamente.
En respuesta al comentario sobre programación dinámica que tiene que ver con "reconsiderar decisiones": Esto obviamente no es cierto para ningún algoritmo de programación dinámico lineal como el problema de subcampo máximo o el problema de Fibonacci anterior.
Esencialmente, imagínese un problema que tiene una subestructura óptima como un gráfico acíclico dirigido cuyos nodos representan subproblemas (donde todo el problema está representado por un nodo cuyo grado de independencia es cero), y cuyos bordes dirigidos representan dependencias entre subproblemas. Entonces, un problema codicioso es un árbol (todos los nodos, excepto la raíz, tienen unidad indegree). Un problema de programación dinámica tiene algunos nodos con un grado mayor que uno. Esto ilustra los subproblemas superpuestos.
Los algoritmos DP usan el hecho de que (para algunos problemas): una solución óptima para un problema de tamaño n se compone de una solución óptima para un problema de tamaño n''<n , y lo usa para construir la solución de abajo hacia arriba, desde el problema más pequeño para el tamaño requerido.
Se ajusta muy bien al mismo principio de recursión (reduce el problema a un sub-problema más pequeño, e invoca recurrentemente), y de hecho, las soluciones DP a menudo se representan como una fórmula recursiva.
Los algoritmos codiciosos están buscando un punto local y haciendo alguna elección con los datos en este momento. Para algunos problemas (el camino más corto sin pesos negativos, por ejemplo), esta elección local dará lugar a una solución óptima.
Un buen ejemplo de las diferencias entre los dos enfoques es el problema de la ruta más corta :
- El algoritmo de Dijsktra es un enfoque codicioso (en cada paso, elija el nodo en el que la ruta de acceso se minimiza actualmente; la elección se realiza de forma codiciosa en función del estado local del algoritmo).
- El algoritmo Bellman-Ford es una solución DP ("relajar" TODAS las aristas reduciendo efectivamente el problema)
Los conceptos de soluciones ambiciosas y dinámicas no son mutuamente excluyentes y creo que esto está causando mucha confusión en la mayoría de las respuestas. Creo que la respuesta de amit hace hincapié en la propiedad más importante: una solución codiciosa toma decisiones basadas en información local . Como consecuencia, una solución codiciosa puede encontrar un óptimo local en lugar de uno global. Las soluciones dinámicas descomponen un problema en subproblemas más pequeños y luego agregan el resultado para obtener la respuesta a un problema más grande y complejo. Entonces, ¿es posible que un problema sea dinámico y codicioso ? La respuesta es - sí, es posible. Un ejemplo sería el algoritmo de Dijkstra. Para este algoritmo, usted toma una decisión codiciosa en cada paso y, sin embargo, reduce el problema a un subproblema más simple.
Todavía hay ejemplos de algoritmos codiciosos que no son DP-s: por ejemplo, el alpinismo es un algoritmo codicioso que no divide un problema en múltiples subproblemas, sino que siempre resuelve uno. También hay ejemplos de DP que no son codiciosos, por ejemplo, calcular el n-ésimo número de Fibonacci utilizando la memorización no es codicioso.
Método codicioso:
- El método codicioso se enfoca en expandir soluciones parcialmente construidas.
- Proporciona muchos resultados, como una solución factible.
- Más eficiente
Programación dinámica:
- Se enfoca en el principio de optimalidad.
- Proporciona respuestas específicas.
- Menos eficiente