¿Cuál es la diferencia entre el algoritmo codicioso y la programación dinámica? ¿Es un programa codicioso un subconjunto de programación dinámica?

Los algoritmos codiciosos son de hecho un caso especial de programación dinámica. Puede consultar los capítulos relevantes de CLRS para obtener información detallada. Aquí intentaré dar una idea general.

En la programación dinámica, examinamos un conjunto de soluciones para problemas más pequeños y elegimos los mejores entre ellos. En un algoritmo codicioso, creemos que una de las soluciones a problemas más pequeños es la óptima (dependiendo de ciertas propiedades del problema) y no examinamos otras soluciones.

A veces es fácil ver una solución DP a un problema, pero se necesita cierta observación para encontrar una solución codiciosa que reduzca la complejidad de tiempo y espacio. Aquí hay un ejemplo: dada una matriz de enteros, encuentre el subconjunto de zig-zag más largo (que puede no ser contagioso). Una solución DP ingenua sería almacenar la submatriz de zig-zag más larga que termina en la posición i en la posición i [i]. Luego use la relación de recurrencia, d [i + 1] = 1 + max {d [j]: j <= i y se mantiene la propiedad zig-zag}. Esto se ejecuta en tiempo O (n ^ 2). Un enfoque codicioso comenzará desde el primer índice y avanzará para incluir un punto donde la 'derivada' cambie de signo. Esto se ejecutará en O (n) tiempo. La elección de elegir y creer que una sub-solución (punto de cambio 'derivado') sea óptima ahorra mucho tiempo aquí, pero es esencialmente solo DP con espacio de muestra de sub-solución podado.

Un algoritmo codicioso es aquel que, en un momento dado, realiza una optimización local. La programación dinámica puede considerarse como una recursión “inteligente”. A menudo se requiere dividir un problema en componentes más pequeños que se pueden almacenar en caché.

Un buen ejemplo de programación dinámica es una función simple:
int fib (int x). Esta función toma un número x y devuelve el x número de Fibonacci. Una solución muy ingenua a este problema tomará tiempo O (fib (x)) debido a llamadas recursivas repetidas, pero con la programación dinámica es posible almacenar en caché las respuestas anteriores y encontrar eficientemente (en tiempo lineal) el número x de fibonacci.

Algoritmo de codicia: el algoritmo de codicia es el que encuentra la solución factible en cada etapa con la esperanza de encontrar una solución óptima global.

Programación dinámica: la programación dinámica es una que divide el problema en una serie de subproblemas superpuestos.

La diferencia entre el método codicioso y la programación dinámica se detalla a continuación:

1. El algoritmo codicioso es uno que encuentra una solución factible en cada etapa con la esperanza de encontrar una solución óptima, mientras que la programación dinámica es una que divide los problemas en una serie de subproblemas superpuestos.
2. El algoritmo codicioso nunca reconsidera sus elecciones, mientras que la programación dinámica puede considerar el estado anterior.
3. El algoritmo codicioso es menos eficiente, mientras que la programación dinámica es más eficiente.
4. El algoritmo codicioso tiene una elección local de los subproblemas, mientras que la programación dinámica resolverá todos los subproblemas y luego seleccionará uno que conduzca a una solución óptima.
5. El algoritmo codicioso toma decisiones en un momento, mientras que la programación dinámica toma decisiones en cada etapa.
6. El algoritmo codicioso funciona según la propiedad de elección, mientras que la programación dinámica funciona según el principio de optimización.
7. El algoritmo codicioso sigue la estrategia de arriba hacia abajo, mientras que la programación dinámica sigue la estrategia de abajo hacia arriba.

Algoritmo codicioso:

• Optimización local
• Todos los problemas no pueden resolverse mediante un algoritmo codicioso.
• Eficiente (tomó menos tiempo)
• Utilización del espacio
• Los algoritmos codiciosos no siempre son confiables
• En la optimización matemática, los algoritmos codiciosos resuelven problemas combinatorios que tienen las propiedades de los matroides.

Algoritmo dinámico:

• Optimización global
• Cada problema puede resolverse mediante un algoritmo codicioso.
• Siempre tomó más e igual tiempo en comparación con el algoritmo codicioso (si existe).
• Tomó más espacio debido a la memorización
• La programación dinámica siempre es confiable
• La programación dinámica es aplicable a problemas que exhiben las propiedades de subproblemas superpuestos y una subestructura óptima.

La dinámica desempeña un papel importante en la programación (especialmente algorítmica) y es la columna vertebral de algunos de los algoritmos más rápidos, mientras que la codicia es muy útil en algunos casos particulares.

Algoritmos codiciosos

Funciona en etapas, en cada etapa se toma una decisión que es buena en ese punto, sin preocuparse por el futuro. Esto significa que se elige el mejor local . “Asume que una buena selección local hace una solución global óptima”.

Las dos propiedades básicas de los algoritmos codiciosos óptimos son:

1. Propiedad de elección codiciosa:
   Esta propiedad dice que se puede obtener una solución globalmente óptima haciendo una solución localmente óptima (codiciosa). La elección realizada por un algoritmo codicioso puede depender de elecciones anteriores pero no del futuro. De manera iterativa, hace una elección codiciosa tras otra y reduce el problema dado a uno más pequeño.
2. Subestructura óptima:
   Un problema exhibe una subestructura óptima si una solución óptima al problema contiene soluciones óptimas a los subproblemas. Eso significa que podemos resolver subproblemas y desarrollar soluciones para resolver problemas más grandes.

Aplicaciones codiciosas:

• Clasificación: clasificación de selección, clasificación topológica
• Colas de prioridad: ordenación del montón
• Algoritmo de compresión de codificación de Huffman
• Algoritmos de Prim y Kruskal
• Ruta ordenada en gráfico ponderado (Dijikstra)
• Problema de cambio de moneda
• Algoritmos de programación de trabajos

Programación dinámica

La programación dinámica y la memorización funcionan juntas. La principal diferencia entre la programación dinámica en blanco y negro y dividir y conquistar es que, en caso de dividir y conquistar, los subproblemas son independientes, como en DP, se producen superposiciones de subproblemas. Al usar la memorización (mantener una tabla), dp reduce la complejidad exponencial a la complejidad polinómica para muchos problemas. Los principales componentes de dp son:

• Recursión: resuelve el problema de forma recursiva.
• Memorización: para almacenar el resultado de problemas ya resueltos.

En general DP = Recursion + Memoization

Propiedades de DP:

• Subestructura óptima: una solución óptima para un problema contiene soluciones óptimas para subproblemas.
• Subproblemas superpuestos: una solución recursiva contiene un pequeño número de subproblemas distintos que se repiten muchas veces.

Aplicaciones dinámicas: ( Aplicaciones bastante extensas que tiene)

La investigación de operaciones
Toma de decisiones
Optimización de consultas
Ingeniería de recursos hídricos
Ciencias económicas
Problemas de operaciones de yacimientos
Reconocimiento de voz conectado
Análisis de estabilidad de taludes
Usando Matlab
Usando Excel
Compromiso de la unidad
Procesamiento de imágenes
Control óptimo de inventario
Problemas operacionales del yacimiento
Sap Abap
Alineación de secuencia
Simulación para la gestión de alcantarillado.
Financiar
Optimización de producción
Algoritmos genéticos para problemas de permutación
Haskell
HTML
Cuidado de la salud
Programación de energía hidroeléctrica
CECEO
Espacio lineal
Indización y consulta XML
Negocio
Bioinformática

(Libros fuente y quora)

Programación dinámica que utiliza el concepto de soluciones de optimización matemática al considerar todas las soluciones posibles de un problema para examinar un conjunto de soluciones a problemas más pequeños y elegir el mejor entre ellos.

Algoritmos codiciosos seleccionamos una solución que causa el mejor movimiento sin considerar la otra solución posible. una estrategia codiciosa en general no produce una solución óptima, pero, sin embargo, una heurística codiciosa puede producir soluciones óptimas a nivel local que se aproximan a una solución óptima global en un tiempo razonable.

La diferencia clave está en el enfoque. Tanto Greedy como Dynamic se utilizan de alguna manera para optimizar la solución recursiva que lleva tiempo exponencial debido a que resuelve el mismo subproblema varias veces desde cero.

Ambos eliminan la recursividad y crean la solución de abajo hacia arriba. Avaricioso, vaya con el enfoque más intuitivo sin tener en cuenta todas las soluciones posibles. DP, por otro lado, busca todas las soluciones posibles y encuentra la mejor respuesta. Es por eso que DP siempre garantiza que dará la solución correcta todo el tiempo, codicioso por otro lado, no siempre puede dar la mejor solución en todos los casos.

Para problemas en los que Greedy puede funcionar, es mejor que DP. Puede aprender más sobre DP en mi libro.

Compre programación dinámica para entrevistas de codificación: un enfoque ascendente para la resolución de problemas Reserve en línea a precios bajos en India

La programación dinámica se aplica al problema de optimización. Tal problema tiene muchas soluciones posibles, cada solución tiene un valor diferente y tenemos que elegir la solución óptima. En esta solución se ve como secuencia de decisión

La programación dinámica, como dividir y conquistar, resuelve el problema como una solución combinada para un subproblema, pero DP es eficaz cuando los subproblemas se superponen, por lo que reutilizamos la solución a los subproblemas.

Mientras que Greedy simplemente eligió una solución que parece mejor en movimiento sin considerar otra solución.

Programación codiciosa
Un algoritmo codicioso es aquel que encuentra una solución óptima en todas y cada una de las etapas con la esperanza de encontrar un óptimo global al final.

Programación dinámica
Un algoritmo dinámico es aplicable a problemas que exhiben subproblemas superpuestos y propiedades de subestructura óptimas.

Diferencia
La principal diferencia es que, la elección realizada por un algoritmo codicioso puede depender de las elecciones realizadas hasta ahora, pero no de elecciones futuras o de todas las soluciones al subproblema. De forma iterativa, hace 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 principal diferencia con la programación dinámica, que es exhaustiva y garantiza 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 anterior, y puede reconsiderar el camino algorítmico de la etapa anterior a la solución.

Fuente: Wikipedia y StackOverflow

En un algoritmo codicioso, podemos hacer la elección que parezca mejor en este momento y luego resolver los subproblemas que surgen más adelante. La elección realizada por un algoritmo codicioso puede depender de las elecciones realizadas hasta ahora, pero no de elecciones futuras o de todas las soluciones al subproblema. Por lo tanto, suponemos que nuestra elección óptima local también será global, pero a veces falla.

Pero, en la programación dinámica, en general, para resolver un problema dado, necesitamos resolver subproblemas, luego combinar las soluciones de los subproblemas para llegar a una solución general. Entonces, la dinámica siempre da una solución global óptima.

Ejemplo: – Problema de gráfico de varias etapas, en el que tenemos que encontrar la ruta más corta desde el origen hasta el destino. Si usamos un algoritmo codicioso aquí, entonces verificamos todos los bordes en cada nodo y tomamos el más corto y usamos solo ese valor para subproblemas posteriores. En este caso, aunque la complejidad temporal es O (E), la solución podría no ser óptima.

Se dice que la programación dinámica se centra en el Principio de deseabilidad, “Una solución óptima para cualquier caso de un problema de optimización está compuesta de soluciones óptimas para su clase abstracta pública”.
Mientras que, la técnica codiciosa se enfoca en expandir soluciones parcialmente construidas hasta llegar a una solución para un problema completo. Luego se dice que debe ser “la mejor opción local entre todas las opciones posibles disponibles en ese paso”.

• La programación codiciosa y dinámica son métodos para resolver problemas de optimización.
• Los algoritmos codiciosos suelen ser más eficientes que las soluciones DP.
• Sin embargo, a menudo necesita usar programación dinámica ya que la solución óptima no puede garantizarse mediante un algoritmo codicioso.
• DP proporciona soluciones eficientes para algunos problemas para los cuales un enfoque de fuerza bruta sería muy lento.
Para utilizar la programación dinámica, solo necesitamos mostrar que el principio de optimización se aplica al problema

En palabras simples, podemos decir que en Dynamic Programming (que tiene problemas para enviar mensajes en la red) primero se puede examinar la ruta que toma el menor tiempo y luego comenzar el viaje,

Por otro lado, el Greedy algorithm toma la optimal decision sobre el terreno sin pensar en el siguiente paso y en el siguiente paso cambia su decisión nuevamente y así sucesivamente …

Notes: Dynamic programming es confiable, mientras que los Algoritmos codiciosos no siempre son confiables

Tarea: termina tu cena

Codicioso: comer postre, plato principal y entrante juntos sin orden. Lo único que tienes en mente es tener comida en tu estómago

Dinámico: tome el primer plato, aumenta su apetito y puede disfrutar mejor el plato principal. Cuando termines con los entrantes, ve a los platos principales. Finalmente, el postre !!!
En la programación dinámica, el problema se divide en varios subproblemas y el resultado del primer subproblema conducirá al resultado del siguiente y así sucesivamente.

¿Diferencia entre método codicioso y programación dinámica?

visto entonces.
Considera este ejemplo.
Estás parado en un lugar p. Tienes que ir a q. Hay lugares intermedios C1, C2 …

Desea minimizar la distancia recorrida.

Método codicioso de resolución
No quieres probar todos los lugares intermedios. Irás al lugar intermedio más cercano. ¿Por qué? Sientes al ir al lugar intermedio más cercano, minimizarás la distancia a q.

Programación dinámica
Intenta todos los lugares, pero almacena el resultado anterior. Por ejemplo: para alcanzar C3 en una distancia mínima, alcanzaste C1. Entonces guardas C1. Entonces, si desea ir a C5, en C3, irá a C1 y luego a C3 y luego comprobará si ir de C3 a C5 es el más cercano.

Le sugiero que lea Introducción a los algoritmos por CLRS para comprender con mayor detalle.

Los encuentro difíciles de comparar. Una diferencia sería que la programación dinámica almacena y utiliza deliberadamente información sobre subproblemas que han sido identificados, mientras que la codiciosa programación no utiliza en absoluto la “experiencia” previa. Utiliza solo lo que ‘sabe’ en la coyuntura actual.