Algoritmo codicioso con ejemplo: qué es, método y enfoque

¿Qué es un algoritmo codicioso?

A Algoritmo codicioso Divide recursivamente un conjunto de recursos en función de la máxima disponibilidad inmediata de ese recurso en cualquier etapa de la ejecución.

Resolver un problema con el enfoque voraz tiene dos etapas:

1. Escaneando la lista de artículos
2. Optimiza

Ambas etapas se ejecutan en paralelo a medida que la matriz de entrada se divide progresivamente.

Para seguir el enfoque voraz, un conocimiento práctico de la recursión y el cambio de contexto te ayudará. trace el código. El paradigma voraz se puede describir con un par de enunciados necesarios y suficientes.

Dos condiciones definen el paradigma codicioso.

• Cada decisión tomada paso a paso debe orientar el problema hacia su solución mejor aceptada.
• La estructura del problema debe detenerse en un número finito de pasos voraces.

Una vez establecida la teoría, veamos la historia que hay detrás del enfoque de búsqueda voraz.

Historia de los codiciosos Algorithms

Estos son los hitos importantes en la historia de los algoritmos voraces:

• Los algoritmos voraces se conceptualizaron por primera vez para algoritmos de recorrido de grafos en la década de 1950.
• Edsger Dijkstra desarrolló su algoritmo de ruta más corta para acortar los recorridos por la capital holandesa, Ámsterdam.
• En esa misma década, Prim y Kruskal desarrollaron estrategias de optimización que minimizan los costes de las rutas ponderadas para construir árboles de expansión mínima.
• En los años 70, los investigadores estadounidenses Cormen, Leiserson, Rivest y Stein describieron la subestructuración recursiva de soluciones voraces en su obra clásica. Introduction to Algorithms libro de texto.
• El paradigma de búsqueda voraz fue catalogado como una estrategia de optimización distinta en los registros del NIST en 2005.
• A día de hoy, protocolos web como Open Shortest Path First (OSPF) y muchos protocolos de conmutación de paquetes utilizan la estrategia voraz para minimizar el tiempo de tránsito en una red.

Estrategias y decisiones codiciosas

La lógica se reduce a una elección binaria en cada etapa —“codicioso” o “no codicioso”— en función de la dirección que tome el algoritmo para avanzar.

Por ejemplo, el algoritmo de Dijkstra identifica hosts en Internet evaluando una función de costo en cada paso. El valor que devuelve la función de costo determina si la siguiente ruta es "codiciosa" o "no codiciosa".

En resumen, un algoritmo deja de ser codicioso en el momento en que da un paso que no es óptimo localmente, y los problemas codiciosos se detienen cuando no es posible dar ningún otro paso codicioso.

Características del algoritmo codicioso

Las características importantes de un algoritmo codicioso son:

• Una lista ordenada de recursos incluye atribuciones de costo o valor que cuantifican las limitaciones del sistema.
• El algoritmo toma la máxima cantidad de recursos dentro del tiempo en que se aplica una restricción.
• Por ejemplo, en un problema de programación de actividades, los costos de los recursos se miden en horas y las actividades deben realizarse en orden secuencial.

¿Por qué utilizar el enfoque codicioso?

Estas son las razones para utilizar el enfoque codicioso:

• El enfoque voraz tiene ventajas e inconvenientes que lo hacen idóneo para la optimización.
• La razón más obvia es generar una solución viable de inmediato. En el problema de selección de actividades que se analiza a continuación, si hay más actividades disponibles antes de que finalice la actividad actual, se pueden programar en el mismo intervalo de tiempo.
• Otra razón es que divide un problema de forma recursiva en función de una condición, sin necesidad de fusionar subsoluciones.
• En el problema de selección de actividades, el paso de división recursiva se logra escaneando la lista una sola vez y considerando solo las actividades elegibles.

Cómo resolver el problema de selección de actividades

En el ejemplo de programación de actividades, cada actividad tiene una hora de inicio y una hora de finalización, y está indexada por un número para su referencia. Hay dos categorías de actividades:

1. Actividad considerada: la actividad de referencia a partir de la cual se mide la capacidad de incorporar más actividades restantes.
2. Actividades restantes: actividades en uno o más índices por delante de la actividad considerada.

El coste de realizar una actividad es su duración, calculada como (fin – inicio).

El margen de tolerancia es simplemente el número de actividades restantes que se pueden realizar dentro del tiempo de una actividad considerada.

Architectura del enfoque codicioso

Paso 1) Examine la lista de costos de actividad comenzando con el índice 0 como índice considerado.

Paso 2) Cuando haya más actividades que puedan finalizar antes de que termine la actividad en cuestión, busque esas actividades restantes.

Paso 3) Si no se pueden programar más actividades, la actividad restante se convierte en la siguiente actividad a considerar. Repita los pasos 1 y 2 con la nueva actividad. Si no quedan actividades, vaya al paso 4.

Paso 4) Devuelve la unión de los índices considerados; estos son los índices de actividad que maximizan el rendimiento.

Architectura del enfoque codicioso

Code Explicación

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

#define MAX_ACTIVITIES 12

Explicación del código:

1. Archivos/clases de encabezado incluidos
2. El número máximo de actividades que puede configurar el usuario.

using namespace std;

class TIME
{
    public:
    int hours;

    public: TIME()
    {
   	 hours = 0;
    }
};

Explicación del código:

1. Declara el espacio de nombres estándar para las operaciones de transmisión.
2. Una definición de clase para TIME
3. Una marca de tiempo de una hora.
4. Un constructor predeterminado de TIME
5. La variable horas.

class Activity
{
    public:
    int index;
    TIME start;
    TIME finish;

    public: Activity()
    {
   	 start = finish = TIME();
    }
};

Explicación del código:

1. Definición de una clase para Activity.
2. Marcas de tiempo que, en conjunto, definen una duración.
3. En el constructor predeterminado, todas las marcas de tiempo se inicializan a 0.

class Scheduler
{
    public:
    int considered_index,init_index;
    Activity *current_activities = new    Activity[MAX_ACTIVITIES];
    Activity *scheduled;

Explicación del código:

1. Parte 1 de la definición de clase de planificador.
2. El índice considerado es el punto de partida para escanear el array.
3. init_index se utiliza para asignar marcas de tiempo aleatorias durante la configuración.
4. Se asigna dinámicamente una matriz de objetos Activity con el operador new.
5. El puntero programado contiene el resultado actual del algoritmo voraz.

Scheduler()
{
   	 considered_index = 0;
   	 scheduled = NULL;
...
...

Explicación del código:

1. El constructor del programador: segunda parte de la definición de la clase.
2. El índice considerado marca el inicio del escaneo actual.
3. El grado de codicia no está definido al principio.

for(init_index = 0; init_index < MAX_ACTIVITIES; init_index++)
 {
   		 current_activities[init_index].start.hours =
   			 rand() % 12;

   		 current_activities[init_index].finish.hours =
   			 current_activities[init_index].start.hours +
   				 (rand() % 2);

   		 printf("\nSTART:%d END %d\n",
   		 current_activities[init_index].start.hours
   		 ,current_activities[init_index].finish.hours);
 }
&#8230;
&#8230;

Explicación del código:

1. Un bucle for inicializa las horas de inicio y finalización de cada actividad programada.
2. Inicializa la hora de inicio.
3. Inicializa la hora de finalización para que sea igual o posterior a la hora de inicio.
4. Una instrucción de depuración imprime las duraciones asignadas.

	public:
   		 Activity * activity_select(int);
};

Explicación del código:

1. Parte 4: la parte final de la definición de la clase Scheduler.
2. activity_select() toma un índice inicial como base y divide la búsqueda voraz en subproblemas.

Activity * Scheduler :: activity_select(int considered_index)
{
    this->considered_index = considered_index;
    int greedy_extent = this->considered_index + 1;
…
…

1. El operador de resolución de ámbito (::) vincula la definición de la función con la clase Scheduler.
2. El valor de considered_index se pasa por valor, y greedy_extent se inicializa con el índice inmediatamente posterior.

Activity * Scheduler :: activity_select(int considered_index)
{
    	while( (greedy_extent < MAX_ACTIVITIES ) &&
   	 ((this->current_activities[greedy_extent]).start.hours <
   		 (this->current_activities[considered_index]).finish.hours ))
    	{
   	 printf("\nSchedule start:%d \nfinish%d\n activity:%d\n",
   	 (this->current_activities[greedy_extent]).start.hours,
   	 (this->current_activities[greedy_extent]).finish.hours,
   	 greedy_extent + 1);
   	 greedy_extent++;
    	}
&#8230;
...

Explicación del código:

1. La lógica principal —el alcance voraz está limitado a MAX_ACTIVITIES—.
2. Se compara la hora de inicio de la actividad actual con la hora de finalización de la actividad considerada.
3. Mientras se cumpla la condición, se imprimirá un mensaje de depuración opcional.
4. El algoritmo de búsqueda avanza entonces al siguiente índice en la matriz de actividades.

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

   	 return activity_select(greedy_extent);
    }
    else
    {
   	 return NULL;
    }
}

Explicación del código:

1. La comprobación condicional verifica si se han cubierto todas las actividades.
2. De lo contrario, el algoritmo reinicia la búsqueda voraz desde el índice actual, un paso recursivo que divide el problema de forma voraz.
3. Si la respuesta es sí, el control regresa a quien realizó la llamada sin posibilidad de extender la codicia.

int main()
{
    Scheduler *activity_sched = new Scheduler();
    activity_sched->scheduled = activity_sched->activity_select(
   				activity_sched->considered_index);
    return 0;
}

Explicación del código:

1. La función principal invoca al planificador.
2. Se instancia un nuevo objeto Scheduler.
3. La función activity_select() devuelve un puntero a Activity al llamador una vez que finaliza la búsqueda codiciosa.

Salida:

START:7 END 7

START:9 END 10

START:5 END 6

START:10 END 10

START:9 END 10

Schedule start:5
finish6
 activity:3

Schedule start:9
finish10
 activity:5

Limitaciones de la técnica codiciosa

El enfoque voraz no es adecuado para problemas que requieren una solución óptima para cada subproblema, como por ejemplo la ordenación.

En estos casos, el método voraz puede ser erróneo; en el peor de los casos, produce una solución no óptima.

El principal inconveniente de los algoritmos voraces es que eligen sin saber qué hay más allá del estado voraz actual.

El siguiente diagrama ilustra esta desventaja del método voraz.

En el escaneo voraz que se muestra aquí como un árbol (un valor más alto significa mayor voracidad), un algoritmo con valor 40 elegiría 29 a continuación, y luego terminaría en 12, para un total de 41.

Por el contrario, una estrategia de divide y vencerás seguiría con 40 después de 25 para un total de 65, lo que supone 24 puntos más que la opción localmente codiciosa.

Ejemplos de codicioso Algorithms

La mayoría de los algoritmos de red se basan en un enfoque voraz. Algunos ejemplos comunes de algoritmos voraces son:

• Algoritmo del árbol de expansión mínima de Prim
• Problema del viajante (aproximado)
• Coloreado de mapas gráficos
• Algoritmo del árbol de expansión mínima de Kruskal
• Algoritmo de ruta más corta de Dijkstra
• Cobertura de vértices de grafos
• Problema de la mochila
• Secuenciación de tareas con plazos de entrega

Preguntas Frecuentes