Un algoritmo Greedy es un paradigma algorítmico que construye una solución pieza por pieza, eligiendo siempre la siguiente pieza que ofrece el beneficio más obvio e inmediato. Por lo tanto, los problemas en los que elegir lo óptimo localmente también conduce a una solución global son los más adecuados para Greedy.
Por ejemplo, considere el problema de la mochila fraccional. La estrategia óptima local es elegir el artículo que tiene la relación valor máximo vs peso. Esta estrategia también conduce a una solución óptima global porque permitimos tomar fracciones de un artículo.
La programación dinámica es principalmente una optimización sobre recursividad simple. Dondequiera que veamos una solución recursiva que tiene llamadas repetidas para las mismas entradas, podemos optimizarla usando Programación Dinámica. La idea es simplemente almacenar los resultados de los subproblemas para que no tengamos que volver a calcularlos cuando sea necesario más adelante. Esta sencilla optimización reduce las complejidades del tiempo de exponencial a polinomial. Por ejemplo, si escribimos una solución recursiva simple para los números de Fibonacci, obtenemos una complejidad de tiempo exponencial y si la optimizamos almacenando soluciones de subproblemas, la complejidad de tiempo se reduce a lineal.
A continuación se muestran algunas de las principales diferencias entre el método Greedy y la programación dinámica:
| Rasgo | método codicioso | Programación dinámica |
|---|---|---|
| Factibilidad | En un Algoritmo codicioso, hacemos la elección que parece mejor en el momento con la esperanza de que nos lleve a una solución global óptima. | En la programación dinámica, tomamos decisiones en cada paso considerando el problema actual y la solución del subproblema resuelto previamente para calcular la solución óptima. |
| Optimalidad | En Greedy Method, a veces no existe tal garantía de obtener la solución óptima. | Se garantiza que la Programación Dinámica generará una solución óptima ya que generalmente considera todos los casos posibles y luego elige la mejor. |
| recursividad | Un método codicioso sigue la heurística de resolución de problemas de hacer la elección localmente óptima en cada etapa. | Una programación dinámica es una técnica algorítmica que suele basarse en una fórmula recurrente que utiliza algunos estados previamente calculados. |
| Memoización | Es más eficiente en términos de memoria, ya que nunca mira hacia atrás ni revisa las elecciones anteriores. | Requiere una tabla dp para la memorización y aumenta la complejidad de la memoria. |
| Complejidad del tiempo | Los métodos codiciosos son generalmente más rápidos. Por ejemplo, el algoritmo de ruta más corta de Dijkstra toma el tiempo O (ELogV + VLogV). | La programación dinámica es generalmente más lenta. Por ejemplo, el algoritmo de Bellman Ford toma el tiempo O(VE). |
| Moda | El método codicioso calcula su solución haciendo sus elecciones de manera serial hacia adelante, nunca mirando hacia atrás ni revisando las elecciones anteriores. | La programación dinámica calcula su solución de abajo hacia arriba o de arriba hacia abajo sintetizándolas a partir de subsoluciones óptimas más pequeñas. |
| Ejemplo | Mochila fraccionada. |
0/1 problema de mochila |
Publicación traducida automáticamente
Artículo escrito por gyanendra371 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA