Algorithme gourmand avec exemple : qu'est-ce que c'est, méthode et approche

Pour comprendre l'approche gourmande, vous devrez avoir une connaissance pratique de la récursivité et du changement de contexte. Cela vous aide à comprendre comment tracer le code. Vous pouvez définir le paradigme gourmand en termes de vos propres déclarations nécessaires et suffisantes.

Deux conditions définissent le paradigme gourmand.

• Chaque solution par étapes doit structurer un problème vers sa solution la mieux acceptée.
• Il suffit que la structuration du problème puisse s’arrêter en un nombre fini d’étapes gourmandes.

La théorie se poursuivant, décrivons l’histoire associée à l’approche de recherche gourmande.

Histoire des gourmands Algorithms

Voici un repère important des algorithmes gloutons :

• Les algorithmes gloutons ont été conceptualisés pour de nombreux algorithmes de marche sur graphes dans les années 1950.
• Esdger Djikstra a conceptualisé l'algorithme pour générer des arbres couvrants minimaux. Son objectif était de réduire la durée des liaisons au sein de la capitale néerlandaise, Amsterdam.
• Au cours de la même décennie, Prim et Kruskal ont mis en place des stratégies d'optimisation basées sur la minimisation des coûts de trajet le long des itinéraires pondérés.
• Dans les années 70, les chercheurs américains Cormen, Rivest et Stein ont proposé une sous-structuration récursive des solutions gloutonnes dans leur livre classique d'introduction aux algorithmes.
• Le paradigme de recherche gourmande a été enregistré comme un type différent de stratégie d'optimisation dans les archives du NIST en 2005.
• Jusqu'à présent, les protocoles qui gèrent le Web, tels que l'OSPF (Open-shortest-path-first) et de nombreux autres protocoles de commutation de paquets réseau, utilisent la stratégie gourmande pour minimiser le temps passé sur un réseau.

Stratégies et décisions avides

La logique dans sa forme la plus simple se résumait à « gourmand » ou « pas gourmand ». Ces déclarations ont été définies par l’approche adoptée pour avancer dans chaque étape de l’algorithme.

Par exemple, l'algorithme de Djikstra a utilisé une stratégie gourmande par étapes identifiant les hôtes sur Internet en calculant une fonction de coût. La valeur renvoyée par la fonction de coût déterminait si le chemin suivant était « gourmand » ou « non gourmand ».

En bref, un algorithme cesse d’être gourmand si, à un moment donné, il franchit une étape qui n’est pas localement gourmande. Les problèmes de cupidité s’arrêtent sans que la cupidité ne prenne plus d’ampleur.

Caractéristiques de l'algorithme gourmand

Les caractéristiques importantes d’un algorithme Greedy sont :

• Il existe une liste ordonnée de ressources, avec des coûts ou des attributions de valeur. Ceux-ci quantifient les contraintes sur un système.
• Vous prendrez la quantité maximale de ressources dans le temps où une contrainte s'applique.
• Par exemple, dans un problème de planification d’activités, les coûts des ressources sont exprimés en heures et les activités doivent être exécutées dans un ordre séquentiel.

Pourquoi utiliser l’approche gourmande ?

Voici les raisons d’utiliser l’approche gourmande :

• L'approche gourmande comporte quelques compromis, ce qui peut la rendre adaptée à l'optimisation.
• L’une des principales raisons est de parvenir immédiatement à la solution la plus réalisable. Dans le problème de sélection d'activité (expliqué ci-dessous), si plusieurs activités peuvent être effectuées avant de terminer l'activité en cours, ces activités peuvent être effectuées dans le même temps.
• Une autre raison est de diviser un problème de manière récursive en fonction d’une condition, sans avoir besoin de combiner toutes les solutions.
• Dans le problème de sélection d'activités, l'étape de « division récursive » est réalisée en parcourant une liste d'éléments une seule fois et en considérant certaines activités.

Comment résoudre le problème de sélection d'activité

Dans l'exemple de planification d'activités, il y a une heure de « début » et de « fin » pour chaque activité. Chaque activité est indexée par un numéro pour référence. Il existe deux catégories d'activités.

1. activité considérée: est l'activité, qui est la référence à partir de laquelle la capacité à faire plus d'une activité restante est analysée.
2. activités restantes : activités à un ou plusieurs indices en avance sur l’activité considérée.

La durée totale donne le coût de réalisation de l'activité. Autrement dit (fin – début) nous donne la durée comme coût d’une activité.

Vous apprendrez que l’étendue gourmande est le nombre d’activités restantes que vous pouvez effectuer pendant la durée d’une activité considérée.

Architecture de l’approche Greedy

ÉTAPE 1) Parcourez la liste des coûts d'activité en commençant par l'indice 0 comme indice considéré.

ÉTAPE 2) Lorsque plusieurs activités peuvent être terminées au moment où l'activité considérée se termine, commencez à rechercher une ou plusieurs activités restantes.

ÉTAPE 3) S'il n'y a plus d'activités restantes, l'activité restante en cours devient la prochaine activité considérée. Répétez l'étape 1 et l'étape 2, avec la nouvelle activité considérée. S'il ne reste plus d'activités, passez à l'étape 4.

ÉTAPE 4 ) Renvoie l'union des indices considérés. Ce sont les indices d’activité qui seront utilisés pour maximiser le débit.

Explication du code

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

#define MAX_ACTIVITIES 12

Explication du code:

1. Fichiers/classes d'en-tête inclus
2. Un nombre maximum d'activités fournies par l'utilisateur.

using namespace std;

class TIME
{
    public:
    int hours;

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

Explication du code:

1. L'espace de noms pour les opérations de streaming.
2. Une définition de classe pour TIME
3. Un horodatage horaire.
4. Un constructeur par défaut TIME
5. Les horaires variables.

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

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

Explication du code:

1. Une définition de classe à partir de l'activité
2. Horodatages définissant une durée
3. Tous les horodatages sont initialisés à 0 dans le constructeur par défaut

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

Explication du code:

1. Partie 1 de la définition de la classe du planificateur.
2. L'index considéré est le point de départ de l'analyse du tableau.
3. L'index d'initialisation est utilisé pour attribuer des horodatages aléatoires.
4. Un tableau d'objets d'activité est alloué dynamiquement à l'aide de l'opérateur new.
5. Le pointeur programmé définit l'emplacement de base actuel de la cupidité.

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

Explication du code:

1. Le constructeur du planificateur – partie 2 de la définition de la classe du planificateur.
2. L'index considéré définit le début actuel du scan en cours.
3. L’étendue gourmande actuelle n’est pas définie au départ.

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);
 }
…
…

Explication du code:

1. Une boucle for pour initialiser les heures de début et de fin de chacune des activités actuellement programmées.
2. Initialisation de l’heure de début.
3. Initialisation de l'heure de fin toujours après ou exactement à l'heure de début.
4. Une instruction de débogage pour imprimer les durées allouées.

	public:
   		 Activity * activity_select(int);
};

Explication du code:

1. Partie 4 – la dernière partie de la définition de la classe du planificateur.
2. La fonction de sélection d'activité prend un index de point de départ comme base et divise la quête gourmande en sous-problèmes gourmands.

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

1. À l’aide de l’opérateur de résolution de portée (::), la définition de la fonction est fournie.
2. L'Indice considéré est l'Indice appelé par valeur. Le greedy_extent est initialisé juste un index après l'index considéré.

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

Explication du code:

1. La logique de base - L'étendue gourmande est limitée au nombre d'activités.
2. Les heures de début de l'activité en cours sont vérifiées comme étant programmables avant la fin de l'activité considérée (donnée par l'index considéré).
3. Tant que cela est possible, une instruction de débogage facultative est imprimée.
4. Passer à l'index suivant sur le tableau d'activité

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

Explication du code:

1. Le conditionnel vérifie si toutes les activités ont été couvertes.
2. Sinon, vous pouvez redémarrer votre gourmand avec l'Index considéré comme point actuel. Il s’agit d’une étape récursive qui divise avidement l’énoncé du problème.
3. Si oui, il revient à l'appelant sans aucune possibilité d'étendre la cupidité.

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

Explication du code:

1. La fonction principale utilisée pour appeler le planificateur.
2. Un nouveau planificateur est instancié.
3. La fonction de sélection d'activité, qui renvoie un pointeur de type activité revient à l'appelant une fois la quête gourmande terminée.

Sortie :

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

Limites de la technique gourmande

Il ne convient pas aux problèmes gourmands où une solution est requise pour chaque sous-problème comme le tri.

Dans de tels problèmes pratiques d’algorithme Greedy, la méthode Greedy peut être erronée ; dans le pire des cas, cela conduit même à une solution non optimale.

Par conséquent, l’inconvénient des algorithmes gloutons est de ne pas savoir ce qui nous attend par rapport à l’état glouton actuel.

Vous trouverez ci-dessous une description des inconvénients de la méthode Greedy :

Dans l'analyse gourmande présentée ici sous la forme d'un arbre (valeur plus élevée, cupidité plus élevée), un état d'algorithme à la valeur : 40 est susceptible de prendre 29 comme valeur suivante. De plus, sa quête se termine à 12. Cela équivaut à une valeur de 41.

Cependant, si l’algorithme empruntait un chemin sous-optimal ou adoptait une stratégie de conquête. alors 25 serait suivi de 40, et l'amélioration globale des coûts serait de 65, ce qui est évalué 24 points de plus comme une décision sous-optimale.

Exemples de gourmands Algorithms

La plupart des algorithmes de mise en réseau utilisent l’approche gloutonne. Voici une liste de quelques exemples d’algorithmes Greedy :

• Algorithme d'arbre couvrant minimal de Prim
• Problème de voyageur de commerce
• Graphique – Coloriage de carte
• Algorithme d'arbre couvrant minimal de Kruskal
• Algorithme d'arbre couvrant minimal de Dijkstra
• Graphique – Couverture des sommets
• Problème de sac à dos
• Problème de planification des tâches

Résumé

Pour résumer, l'article a défini le paradigme glouton, a montré comment l'optimisation gloutonne et la récursivité peuvent vous aider à obtenir la meilleure solution jusqu'à un certain point. L'algorithme Greedy est largement utilisé pour la résolution de problèmes dans de nombreux langages sous le nom d'algorithme Greedy. Python, C, C#, PHP, Java, etc. La sélection d'activité de l'exemple d'algorithme gourmand a été décrite comme un problème stratégique qui pourrait atteindre un débit maximal en utilisant l'approche gourmande. En fin de compte, les inconvénients du recours à l’approche gourmande ont été expliqués.