El algoritmo codicioso se define como un método para resolver problemas de optimización tomando decisiones que produzcan el beneficio más obvio e inmediato, independientemente del resultado final. Funciona para casos en los que: minimización o maximización lleva a la solución deseada.
Características del algoritmo Greedy
Para resolver un problema utilizando el enfoque Greedy, debe cumplir con algunas características importantes:
- Hay una lista ordenada de recursos (ganancia, costo, valor, etc.)
- Se utiliza el máximo de todos los recursos (beneficio máximo, valor máximo, etc.).
- Por ejemplo, en el problema de la mochila fraccionada, primero se toma el valor/peso máximo en función de la capacidad disponible.
Introducción a los algoritmos codiciosos – Estructuras de datos y tutoriales de algoritmos
Todos los algoritmos codiciosos siguen una estructura básica:
- Declarar un resultado vacío = 0.
- Hacemos una elección codiciosa para seleccionar, si la elección es factible, la agregamos al resultado final.
- el resultado de vuelta.
¿Por qué elegir el enfoque codicioso?
El enfoque codicioso tiene algunas compensaciones, que pueden hacerlo adecuado para la optimización. Una razón importante es llegar de inmediato a la solución más factible. En el problema de selección de actividades (explicado a continuación), si se pueden realizar más actividades antes de que se complete la actividad actual, entonces esas actividades se pueden realizar en el mismo tiempo. Otra razón es dividir recursivamente un problema basado en una condición, sin tener que combinar todas las soluciones. En el problema de selección de actividades, el paso de «división recursiva» se logra escaneando una lista de elementos solo una vez y considerando ciertas actividades.
Ejemplo de algoritmo codicioso:
Algunos problemas famosos que surgen: Propiedad de subestructura óptima y se pueden resolver usando el enfoque Greedy son:
1) Problema de secuencia de tareas:
Elija con entusiasmo los trabajos con el máximo beneficio primero, clasificando los trabajos en orden descendente de su beneficio. Esto ayudaría a maximizar el beneficio general, ya que elegir la pista con el máximo beneficio para cada intervalo de tiempo maximizará en última instancia el beneficio total.
2) Algoritmo de Prim para encontrar el árbol de expansión mínimo:
Comienza con un árbol de expansión vacío. La idea es mantener dos conjuntos de vértices. El primer conjunto contiene los vértices que ya están incluidos en el MST, el otro conjunto contiene los vértices que aún no se han incluido. En cada paso, tiene en cuenta todas las aristas que conectan los dos conjuntos y elige la arista de peso mínimo de estas aristas. Después de elegir el borde, el otro punto final del borde se mueve al conjunto con MST.
¿Cómo funciona el algoritmo codicioso?
Cuando la elección de aplicar el método codicioso se hace sin realizar una investigación exhaustiva, la decisión de utilizarlo puede ser algo difícil y, en ocasiones, incluso conducir al fracaso. En algunos casos, tomar la mejor opción local puede conducir a la pérdida de la solución óptima global.
Por ejemplo:
Gráfico de vértices ponderados
- En el gráfico anterior, comenzando en el nodo raíz 10 si seleccionamos ansiosamente el siguiente nodo para obtener la ruta más ponderada, el siguiente nodo seleccionado será 5 que traerá la suma total 15 y el camino terminará porque no hay hijo de 5 pero el camino 10 -> 5 no es la ruta de peso máximo.
El enfoque codicioso falló
- Para encontrar la ruta más ponderada, se deben calcular todos los pad sum posibles y se debe comparar su pad sum para obtener el resultado deseado. Se puede ver que la ruta más ponderada en el gráfico anterior es 10 -> 1 -> 30 que da el padsom 41.
enfoque correcto
- En tales casos, el enfoque codicioso no funcionaría en lugar de caminos completos de zanahoria Hasta que nudo de hoja debe tenerse en cuenta para obtener la respuesta correcta, es decir, la ruta más ponderada. Esto se puede lograr comprobando recursivamente todas las rutas y calculando su peso.
Asi que para usar el algoritmo Greedy, el problema no debe contener: subproblemas superpuestos.
El algoritmo Greedy y la programación dinámica son dos de los paradigmas de algoritmos más utilizados para resolver problemas de programación complejos, mientras que el enfoque Greedy funciona para problemas en los que localmente óptimo la elección conduce a una solución óptima global La programación dinámica funciona para problemas con: subproblemas superpuestos estructura donde se necesita una respuesta a un subproblema para resolver varios otros subproblemas. Las diferencias detalladas se dan en la siguiente tabla:
Rasgo | Algoritmo codicioso | Programación dinámica |
|---|---|---|
Factibilidad | En un algoritmo codicioso, tomamos la decisión que parece mejor en ese momento, con la esperanza de que conduzca a una solución global óptima. | En la programación dinámica, tomamos una decisión en cada paso, teniendo en cuenta el problema actual y la solución a un subproblema previamente resuelto para calcular la solución óptima. |
Optimalidad | En Greedy Method a veces no existe tal garantía para obtener una 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 el mejor. |
Repetición | Un método codicioso sigue la heurística de resolución de problemas de hacer la elección localmente óptima en cada etapa. | La programación dinámica es una técnica algorítmica que suele basarse en una fórmula recurrente que utiliza una serie de estados previamente calculados. |
Memorizar | Es más eficiente en términos de memoria porque nunca mira hacia atrás ni revisa las elecciones anteriores. | Requiere una tabla de programación dinámica para el almacenamiento de memoria 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: O(ELogV + VLogV) tiempo. | La programación dinámica es generalmente más lenta. Por ejemplo, el algoritmo de Bellman Ford toma: O(VE) tiempo. |
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ándola a partir de subsoluciones óptimas más pequeñas. |
Ejemplo | Mochila fraccionada. | 0/1 problema de mochila |
Algunas de las cuestiones populares sobre el enfoque codicioso que se preguntan con frecuencia en las entrevistas son:
- Problema de selección de actividad
- Algoritmo de árbol de expansión mínimo de Kruskal
- Codificación de Huffman
- Codificación eficiente de Huffman para entradas ordenadas
- Algoritmo de árbol de expansión mínimo de Prim
- MST de Prim para visualización de lista adyacente
- Algoritmo de ruta más corta de Dijkstra
- Algoritmo de visualización de lista adyacente de Dijkstra
- Problema con el orden de las tareas
- Algoritmo codicioso para encontrar el número mínimo de monedas
- Problema del centro K
- Número mínimo de andenes necesarios para una estación de tren/autobús
- Conecte n cuerdas con un costo mínimo
- Colores del gráfico
- Problema de la mochila fraccionada
- Minimizar el flujo de efectivo entre un determinado grupo de amigos que se han prestado dinero entre sí
- Encuentre el tiempo mínimo para completar todas las tareas con ciertas restricciones
- Encuentra la suma máxima igual a la suma de tres montones
- Algoritmo de Dail
- Algoritmo de Boruvka.
Beneficios del enfoque codicioso:
- El enfoque codicioso es fácil de implementar.
- Suelen tener menor complejidad temporal.
- Los algoritmos codiciosos se pueden usar con fines de optimización o para encontrar una optimización cercana en el caso de problemas difíciles.
Desventajas del enfoque codicioso:
- La solución óptima local puede no ser siempre la óptima global.