logo

TechCodeview

Algoritmos codiciosos

Algoritmos codiciosos son una clase de algoritmos que hacen localmente óptimo opciones en cada paso con la esperanza de encontrar una óptimo global solución. En estos algoritmos las decisiones se toman en base a la información disponible en el momento actual sin considerar las consecuencias de estas decisiones en el futuro. La idea clave es seleccionar la mejor opción posible en cada paso, lo que lleva a una solución que puede no siempre ser la más óptima pero que a menudo es lo suficientemente buena para muchos problemas.

np.sum

En este artículo, entenderemos los algoritmos codiciosos con ejemplos. También veremos los problemas y sus soluciones utilizando el enfoque codicioso.

Algoritmos codiciosos



Tabla de contenidos

¿Qué es el algoritmo codicioso?

A algoritmo codicioso Es un tipo de algoritmo de optimización que toma decisiones localmente óptimas en cada paso para encontrar una solución globalmente óptima. Opera según el principio de tomar la mejor opción ahora sin considerar las consecuencias a largo plazo.

Para aprender qué es el método codicioso y cómo utilizar el enfoque codicioso, lea el tutorial proporcionado sobre el algoritmo codicioso:

Pasos para crear un algoritmo codicioso

Los pasos para definir un algoritmo codicioso son:

  1. Define el problema: Establecer claramente el problema a resolver y el objetivo a optimizar.
  2. Identifique la elección codiciosa: Determine la opción local óptima en cada paso según el estado actual.
  3. Haz la elección codiciosa: Seleccione la opción codiciosa y actualice el estado actual.
  4. Repetir: Continúe tomando decisiones codiciosas hasta llegar a una solución.

Siguiendo los pasos dados, se puede aprender a utilizar algoritmos codiciosos para encontrar soluciones óptimas.

Ejemplos de algoritmos codiciosos

Los ejemplos de algoritmos codiciosos son la mejor manera de comprender el algoritmo. Algunos ejemplos de algoritmos codiciosos de la vida real son:

  • Mochila fraccionaria : Optimiza el valor de los artículos que pueden incluirse fraccionadamente en una mochila con capacidad limitada.
  • El algoritmo de Dijkstra : Encuentra la ruta más corta desde un vértice de origen a todos los demás vértices en un gráfico ponderado.
  • El algoritmo de Kruskal : Encuentra el árbol de expansión mínimo de un gráfico ponderado.
  • Codificación Huffman : Comprime datos asignando códigos más cortos a símbolos más frecuentes.

Aplicaciones del algoritmo codicioso

Hay muchos Aplicaciones del método codicioso en DAA. . Algunas aplicaciones importantes de algoritmos codiciosos son:

  • Asignar tareas a los recursos para minimizar el tiempo de espera o maximizar la eficiencia.
  • Seleccionar los objetos más valiosos para meterlos en una mochila con capacidad limitada.
  • Dividir una imagen en regiones con características similares.
  • Reducir el tamaño de los datos eliminando información redundante.

Desventajas/Limitaciones del uso de un algoritmo codicioso

A continuación se presentan algunas desventajas del algoritmo codicioso:

  • Es posible que los algoritmos codiciosos no siempre encuentren la mejor solución posible.
  • El orden en el que se consideran los elementos puede afectar significativamente el resultado.
  • Los algoritmos codiciosos se centran en optimizaciones locales y pueden pasar por alto mejores soluciones que requieren considerar un contexto más amplio.
  • Los algoritmos codiciosos no son aplicables a problemas en los que la elección codiciosa no conduce a una solución óptima.

Conceptos básicos del algoritmo codicioso:

  • Algoritmos codiciosos (estructura general y aplicaciones)
  • Diferencia entre el algoritmo codicioso y el algoritmo divide y vencerás
  • Enfoque codicioso versus programación dinámica
  • Comparación entre el algoritmo de programación dinámica, divide y vencerás y codicioso

Algoritmos codiciosos estándar:

  • Problema de selección de actividades
  • Problema de secuenciación de trabajos
  • Codificación Huffman
  • Decodificación de Huffman
  • Problema de conexión de agua
  • Swaps mínimos para el equilibrio de soporte
  • Fracción egipcia
  • Los policías atrapan a los ladrones.
  • Problema de colocación de estantes
  • Asignar ratones a los agujeros

Problemas codiciosos en la matriz:

  • Subconjunto mínimo de productos de una matriz
  • Maximizar la suma de la matriz después de K negaciones usando Clasificación
  • Suma mínima del producto de dos matrices.
  • Suma mínima de diferencia absoluta de pares de dos matrices
  • Incremento/disminución mínimo para hacer que la matriz no sea creciente
  • Ordenar matriz con reversa alrededor del medio
  • Suma de áreas de rectángulos posibles para una matriz
  • La mayor matriz lexicográfica con como máximo K intercambios consecutivos
  • Dividir en dos subconjuntos de longitudes k y (N – k) de modo que la diferencia de sumas sea máxima

Problemas codiciosos en el sistema operativo:

  • Algoritmo de primer ajuste en gestión de memoria
  • Algoritmo de mejor ajuste en gestión de memoria
  • Algoritmo de peor ajuste en la gestión de la memoria
  • Primera programación del trabajo más corto
  • Programación de trabajos con dos trabajos permitidos a la vez
  • Programa para el algoritmo de reemplazo de página óptimo

Problemas codiciosos en el gráfico:

  • Árbol de expansión mínima de Kruskal
  • Árbol de expansión mínima de Prim
  • Árbol de expansión mínima de Boruvka
  • Algoritmo de ruta más corta de Dijkastra
  • Algoritmo de dial
  • Costo mínimo para conectar todas las ciudades.
  • Introducción al problema de flujo máximo
  • Número de componentes de un solo ciclo en un gráfico no dirigido

Algoritmo codicioso aproximado para NP completo:

  • Establecer problema de portada
  • Problema de embalaje del contenedor
  • Coloración de gráficos
  • problema de los centros K
  • Problema de supercuerdas más corto
  • Solución aproximada para el problema del viajante utilizando MST

Codiciosos de casos especiales de DP:

  • Problema de mochila fraccionada
  • Número mínimo de monedas requeridas

Problemas fáciles en Greedy Algoritmo :

  • Dividir n en números compuestos máximos
  • Compre acciones máximas si se pueden comprar i acciones el i-ésimo día
  • Encuentra la cantidad mínima y máxima para comprar todos los N dulces
  • Suma máxima posible igual a la suma de tres pilas
  • Divida el cuboide en cubos de modo que la suma de volúmenes sea máxima.
  • Número máximo de clientes que pueden estar satisfechos con una cantidad determinada.
  • Rotaciones mínimas para desbloquear una cerradura circular
  • Salas mínimas para m eventos de n lotes con un horario determinado
  • Costo mínimo para hacer que el tamaño de la matriz sea 1 eliminando pares más grandes
  • Costo mínimo para adquirir todas las monedas con k monedas adicionales permitidas con cada moneda
  • Incremento mínimo en k operaciones para hacer que todos los elementos sean iguales
  • Encuentre el número mínimo de billetes y valores que sumen una cantidad determinada
  • Subconjunto más pequeño con suma mayor que todos los demás elementos

Problemas medios en codiciosos Algoritmo :

  • Máximo de trenes para los que se puede realizar la parada
  • Términos mínimos de Fibonacci con suma igual a K
  • Divida 1 an en dos grupos con una diferencia de suma mínima
  • Papel cortado en un número mínimo de cuadrados.
  • Diferencia mínima entre grupos de tamaño dos
  • Conecte n cuerdas con un costo mínimo.
  • Número mínimo de andenes necesarios para una estación de tren/autobús
  • Vértices iniciales mínimos para atravesar la matriz completa con condiciones dadas
  • Número palindrómico más grande permutando dígitos
  • Encuentre el número más pequeño con un número determinado de dígitos y suma de dígitos
  • Subsecuencia lexicográficamente más grande tal que cada carácter aparece al menos k veces

Problemas difíciles en codiciosos Algoritmo :

  • Elementos máximos que se pueden igualar con k actualizaciones
  • Minimizar el flujo de caja entre amigos
  • Costo mínimo para cortar un tablero en cuadrados
  • Costo mínimo para procesar m tareas donde cambiar cuesta
  • Tiempo mínimo para terminar todos los trabajos con restricciones dadas
  • Minimizar al máximo la diferencia entre las alturas de las torres.
  • Bordes mínimos para invertir para hacer una ruta desde un origen a un destino
  • Encuentre el cubo más grande formado eliminando los dígitos mínimos de un número
  • Reorganice los caracteres en una cadena de modo que no haya dos adyacentes iguales
  • Reorganice una cadena para que todos los mismos caracteres queden a una distancia d
  • Aprenda la estructura de datos y los algoritmos | Tutorial de DSA
  • Las 20 preguntas principales de la entrevista sobre algoritmos codiciosos
  • 'Problemas de práctica' sobre algoritmos codiciosos
  • 'Prueba' sobre algoritmos codiciosos