algorithm - how - ¿Cuál es la diferencia entre la programación dinámica y el enfoque codicioso?
max hashtags instagram 2018 (4)
¿Cuál es la principal diferencia entre la programación dinámica y el enfoque codicioso en términos de uso?
Por lo que yo entiendo, el enfoque codicioso a veces da una solución óptima; en otros casos, el enfoque de programación dinámica brinda una solución óptima.
¿Hay alguna condición particular que deba cumplirse para usar un enfoque (u otro) para obtener una solución óptima?
La diferencia entre el método codicioso y la programación dinámica se da a continuación:
El método codicioso nunca reconsidera sus elecciones, mientras que la programación dinámica puede considerar el estado anterior.
El algoritmo codicioso es menos eficiente mientras que la programación dinámica es más eficiente.
El algoritmo codicioso tiene una elección local de los sub-problemas, mientras que la programación dinámica resolvería todos los sub-problemas y luego seleccionaría uno que conduzca a una solución óptima.
El algoritmo codicioso toma la decisión de una vez, mientras que la programación dinámica toma la decisión en cada etapa.
Me gustaría citar un párrafo que describe la principal diferencia entre los algoritmos codiciosos y los algoritmos de programación dinámica establecidos en el libro Introducción a los algoritmos (3ª edición) de Cormen, Capítulo 15.3, página 381:
Una gran diferencia entre los algoritmos codiciosos y la programación dinámica es que en lugar de encontrar primero soluciones óptimas para subproblemas y luego tomar una decisión informada, los algoritmos codiciosos primero hacen una elección codiciosa , la que se ve mejor en ese momento, y luego resuelven un subproblema resultante. sin molestarse en resolver todos los posibles subproblemas menores relacionados.
Basado en los artículos de Wikipedia.
Enfoque codicioso
Un algoritmo codicioso es un algoritmo que sigue la heurística de resolución de problemas de hacer la elección localmente óptima en cada etapa con la esperanza de encontrar un óptimo global. En muchos problemas, una estrategia codiciosa generalmente no produce una solución óptima, pero una heurística codiciosa puede ofrecer soluciones locales óptimas que se aproximan a una solución óptima global en un tiempo razonable.
Podemos hacer la elección que sea mejor en este momento y luego resolver los subproblemas que surjan más tarde. 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.
Programación dinámica
La idea detrás de la programación dinámica es bastante simple. En general, para resolver un problema determinado, debemos resolver diferentes partes del problema (subproblemas), luego combinar las soluciones de los subproblemas para alcanzar una solución general . A menudo, cuando se usa un método más ingenuo, muchos de los subproblemas se generan y resuelven muchas veces. El enfoque de programación dinámica busca resolver cada subproblema solo una vez , reduciendo así el número de cálculos: una vez que se ha calculado la solución a un subproblema dado, se almacena o "memoriza": la próxima vez que se necesite la misma solución, simplemente se mira hacia arriba. Este enfoque es especialmente útil cuando el número de subproblemas que se repiten crece exponencialmente en función del tamaño de la entrada.
Diferencia
Propiedad codiciosa elección
Podemos hacer la elección que sea mejor en este momento y luego resolver los subproblemas que surjan más tarde. 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.
Por ejemplo, supongamos que tiene que ir del punto A al punto B lo más rápido posible, en una ciudad determinada, durante la hora pico. Un algoritmo de programación dinámica examinará todo el informe de tráfico, estudiando todas las combinaciones posibles de carreteras que podría tomar, y solo entonces le dirá qué camino es el más rápido. Por supuesto, es posible que tenga que esperar un tiempo hasta que el algoritmo finalice, y solo entonces puede comenzar a conducir. La ruta que tomará será la más rápida (suponiendo que nada haya cambiado en el entorno externo).
Por otro lado, un algoritmo codicioso lo pondrá en marcha inmediatamente y escogerá el camino que se vea más rápido en cada intersección. Como se puede imaginar, esta estrategia puede no llevar al tiempo de llegada más rápido, ya que puede tomar algunas calles "fáciles" y luego encontrarse irremediablemente atrapado en un atasco de tráfico.
Algunos otros detalles ...
En la optimización matemática, los algoritmos codiciosos resuelven problemas combinatorios que tienen las propiedades de los matroids .
La programación dinámica es aplicable a problemas que exhiben las propiedades de subproblemas superpuestos y subestructura óptima .
En palabras simples, podemos decir que en Dynamic Programming (que tiene un problema al enviar un mensaje en la red) uno puede primero examinar el camino que toma el tiempo más corto 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 una vez más y así sucesivamente ...
Notes: Dynamic programming es confiable, mientras que los algoritmos codiciosos no siempre son confiables.