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

Para comprender el enfoque codicioso, necesitará tener conocimientos prácticos de recursividad y cambio de contexto. Esto le ayuda a comprender cómo rastrear el código. Puedes definir el paradigma codicioso en términos de tus propias declaraciones necesarias y suficientes.

Dos condiciones definen el paradigma codicioso.

• Cada solución paso a paso debe estructurar un problema hacia su solución mejor aceptada.
• Es suficiente que la estructuración del problema pueda detenerse en un número finito de pasos codiciosos.

Continuando con la teorización, describamos la historia asociada con el enfoque de búsqueda codiciosa.

Historia de los codiciosos Algorithms

He aquí un hito importante de los algoritmos codiciosos:

• Los algoritmos codiciosos se conceptualizaron para muchos algoritmos de recorrido por gráficos en la década de 1950.
• Esdger Djikstra conceptualizó el algoritmo para generar árboles de expansión mínimos. Su objetivo era acortar el tramo de rutas dentro de la capital holandesa, Ámsterdam.
• En la misma década, Prim y Kruskal lograron estrategias de optimización que se basaban en minimizar los costes de los trayectos a lo largo de rutas ponderadas.
• En los años 70, los investigadores estadounidenses Cormen, Rivest y Stein propusieron una subestructuración recursiva de soluciones voraces en su clásico libro de introducción a los algoritmos.
• El paradigma de búsqueda codicioso se registró como un tipo diferente de estrategia de optimización en los registros del NIST en 2005.
• Hasta la fecha, los protocolos que ejecutan la web, como OSPF (open-shortest-path-path-first) y muchos otros protocolos de conmutación de paquetes de red, utilizan la estrategia codiciosa para minimizar el tiempo invertido en una red.

Estrategias y decisiones codiciosas

La lógica en su forma más sencilla se reducía a "codicioso" o "no codicioso". Estas declaraciones estuvieron definidas por el enfoque adoptado para avanzar en cada etapa del algoritmo.

Por ejemplo, el algoritmo de Djikstra utilizó una estrategia voraz por pasos que identificaba hosts en Internet calculando una función de costo. El valor devuelto por la función de costo determinaba si la siguiente ruta era “voraz” o “no voraz”.

En resumen, un algoritmo deja de ser codicioso si en cualquier etapa da un paso que no es localmente codicioso. Los problemas de los codiciosos se detienen sin más alcance de la avaricia.

Características del algoritmo codicioso

Las características importantes de un algoritmo codicioso son:

• Hay una lista ordenada de recursos, con costos o atribuciones de valor. Estos cuantifican las restricciones de un sistema.
• Tomará la cantidad máxima de recursos en el tiempo que se aplique una restricción.
• Por ejemplo, en un problema de programación de actividades, los costos de los recursos se expresan en horas y las actividades deben realizarse en orden serial.

¿Por qué utilizar el enfoque codicioso?

Estas son las razones para utilizar el enfoque codicioso:

• El enfoque codicioso tiene algunas desventajas, que pueden hacerlo adecuado para la optimización.
• Una razón importante es lograr de inmediato 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 finalizar la actividad actual, estas actividades se pueden realizar al mismo tiempo.
• Otra razón es dividir un problema de forma recursiva en función de una condición, sin necesidad de 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.

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

En el ejemplo de programación de actividades, hay una hora de "inicio" y "finalización" para cada actividad. Cada Actividad está indexada por un número como referencia. Hay dos categorías de actividades.

1. actividad considerada: es la Actividad, que es la referencia a partir de la cual se analiza la capacidad de realizar más de una Actividad restante.
2. actividades restantes: actividades en uno o más índices por delante de la actividad considerada.

La duración total da el coste de realizar la actividad. Es decir (final – inicio) nos da la duración como costo de una actividad.

Aprenderá que la extensión codiciosa es la cantidad de actividades restantes que puede realizar en el tiempo de una actividad considerada.

ArchiEstructura del enfoque codicioso.

PASO 1) Escanee la lista de costos de actividad, comenzando con el índice 0 como índice considerado.

PASO 2) Cuando se puedan finalizar más actividades para el momento en que finalice la actividad considerada, comience a buscar una o más actividades restantes.

PASO 3) Si no quedan más actividades restantes, la actividad restante actual se convierte en la siguiente actividad considerada. Repita el paso 1 y el paso 2, con la nueva actividad considerada. Si no quedan actividades restantes, vaya al paso 4.

ETAPA 4 ) Devuelve la unión de los índices considerados. Estos son los índices de actividad que se utilizarán para maximizar el rendimiento.

Explicación del código

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

#define MAX_ACTIVITIES 12

Explicación del código:

1. Archivos/clases de encabezado incluidos
2. Un número máximo de actividades proporcionadas por el usuario.

using namespace std;

class TIME
{
    public:
    int hours;

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

Explicación del código:

1. El espacio de nombres para operaciones de streaming.
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. Una definición de clase a partir de la actividad.
2. Marcas de tiempo que definen una duración
3. Todas las marcas de tiempo se inicializan a 0 en el constructor predeterminado.

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 matriz.
3. El índice de inicialización se utiliza para asignar marcas de tiempo aleatorias.
4. Una matriz de objetos de actividad se asigna dinámicamente utilizando el operador new.
5. El puntero programado define la ubicación base actual de la codicia.

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

Explicación del código:

1. El constructor del programador: parte 2 de la definición de la clase del programador.
2. El índice considerado define el inicio actual del escaneo actual.
3. La extensión codiciosa actual no está definida 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);
 }
…
…

Explicación del código:

1. Un bucle for para inicializar las horas de inicio y finalización de cada una de las actividades actualmente programadas.
2. Inicialización de la hora de inicio.
3. Inicialización de la hora de finalización siempre después o exactamente a la hora de inicio.
4. Una declaración de depuración para imprimir las duraciones asignadas.

	public:
   		 Activity * activity_select(int);
};

Explicación del código:

1. Parte 4: la última parte de la definición de la clase del planificador.
2. La función de selección de actividad toma un índice de punto de partida como base y divide la búsqueda codiciosa en subproblemas codiciosos.

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

1. Utilizando el operador de resolución de alcance (::), se proporciona la definición de la función.
2. El Índice considerado es el Índice denominado por valor. greedy_extent se inicializa solo un índice después del índice considerado.

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++;
    	}
…
...

Explicación del código:

1. La lógica central: la extensión codiciosa se limita al número de actividades.
2. Las horas de inicio de la Actividad actual se marcan como programables antes de que finalice la Actividad considerada (dada por el índice considerado).
3. Siempre que esto sea posible, se imprime una declaración de depuración opcional.
4. Avanzar 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. El condicional comprueba si se han cubierto todas las actividades.
2. De lo contrario, puede reiniciar su codicioso con el Índice considerado como punto actual. Este es un paso recursivo que divide con avidez el planteamiento del problema.
3. En caso afirmativo, regresa a la persona que llama 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 utilizada para invocar el planificador.
2. Se crea una instancia de un nuevo Programador.
3. La función de selección de actividad, que devuelve un puntero de tipo actividad, regresa a la persona que llama una vez finalizada 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

No es adecuado para problemas codiciosos en los que se requiere una solución para cada subproblema, como la clasificación.

En tales problemas de práctica del algoritmo Greedy, el método Greedy puede ser incorrecto; en el peor de los casos, incluso conducen a una solución no óptima.

Por lo tanto, la desventaja de los algoritmos codiciosos es que no saben qué hay por delante del estado codicioso actual.

A continuación se muestra una descripción de la desventaja del método Greedy:

En el escaneo codicioso que se muestra aquí como un árbol (a mayor valor, mayor avaricia), es probable que un estado de algoritmo en el valor: 40 tome 29 como siguiente valor. Además, su misión termina en 12. Esto equivale a un valor de 41.

Sin embargo, si el algoritmo tomó un camino subóptimo o adoptó una estrategia de conquista. luego a 25 le seguirían 40, y la mejora general de costos sería 65, lo que se valora 24 puntos más como una decisión subóptima.

Ejemplos de codicioso Algorithms

La mayoría de los algoritmos de redes utilizan el enfoque voraz. A continuación, se incluye una lista de algunos ejemplos de algoritmos voraces:

• Algoritmo de árbol de expansión mínima de Prim
• Problema de vendedor ambulante
• Gráfico – Mapa para colorear
• Algoritmo de árbol de expansión mínima de Kruskal
• Algoritmo de árbol de expansión mínima de Dijkstra
• Gráfico – Cubierta de vértice
• Problema de la mochila
• Problema de programación de trabajos

Resumen

En resumen, el artículo definió el paradigma voraz y mostró cómo la optimización voraz y la recursión pueden ayudar a obtener la mejor solución hasta cierto punto. El algoritmo voraz se utiliza ampliamente para la resolución de problemas en muchos lenguajes como algoritmo voraz. Python, C, C#, PHP, Java, etc. La selección de actividad del ejemplo del algoritmo codicioso se describió como un problema estratégico que podría lograr el máximo rendimiento utilizando el enfoque codicioso. Al final, se explicaron los inconvenientes del uso del enfoque codicioso.