Elementos básicos del algoritmo codicioso: propiedad de selección codiciosa y propiedad de subestructura óptima.
1. Propiedad de selección codiciosa
La llamada propiedad de selección codiciosa significa que la solución óptima general al problema se puede lograr a través de una serie de elecciones óptimas locales, es decir, codiciosas. selección. Este es el primer elemento básico que hace factible el algoritmo codicioso, y también es la principal diferencia entre el algoritmo codicioso y el algoritmo de programación dinámica.
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, tomando decisiones codiciosas sucesivas de manera iterativa. Reduce el problema a subproblemas más pequeños. Para un problema específico, para determinar si tiene propiedades de elección codiciosa, se debe demostrar que la elección codiciosa realizada en cada paso conduce en última instancia a la solución óptima general del problema.
2. Propiedades óptimas de la subestructura
Cuando la solución óptima de un problema contiene las soluciones óptimas de sus subproblemas, se dice que el problema tiene propiedades óptimas de la subestructura. La propiedad de subestructura óptima de un problema es una característica clave del problema que se puede resolver mediante programación dinámica o algoritmos codiciosos.
Las limitaciones y el proceso de análisis del algoritmo codicioso
1. Las limitaciones del algoritmo codicioso:
El algoritmo codicioso tiene sus limitaciones. Es una solución óptima local, pero no es la solución óptima a nivel global, al igual que el problema del cambio de monedas. Pero aún podemos usar las ideas de programación dinámica que aprendimos en el capítulo anterior para resolverlo.
2. Proceso de análisis del algoritmo codicioso:
En primer lugar, debemos determinar nuestra estrategia codiciosa. Solo la estrategia codiciosa correcta puede sacar nuestra conclusión.