La diferencia entre programación dinámica y algoritmos codiciosos

La diferencia entre programación dinámica y algoritmo codicioso

1. En el algoritmo de programación dinámica, la elección realizada en cada paso a menudo depende de la solución del subproblema relevante. sólo después de resolver el subproblema relevante. Sólo se puede tomar una decisión cuando surge el problema. El algoritmo codicioso solo toma la mejor elección en el estado actual, es decir, la elección óptima local, y luego resuelve los subproblemas correspondientes generados después de hacer esta elección.

2. Los algoritmos de programación dinámica generalmente resuelven cada subproblema de abajo hacia arriba, mientras que los algoritmos codiciosos generalmente resuelven cada subproblema de arriba hacia abajo.

***Mismo punto: ambos tienen propiedades de subestructura óptimas

La idea básica del algoritmo de programación dinámica es similar al método de divide y vencerás, que también descompone el problema a resolver en varias subestructuras Problema (etapa), resuelva las subetapas en orden, la solución del subproblema anterior proporciona información útil para la solución del subproblema posterior. Al resolver cualquier subproblema, enumere varias soluciones locales posibles, conserve aquellas soluciones locales que probablemente sean óptimas a través de la toma de decisiones y descarte otras soluciones locales.