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

Qu’est-ce qu’un algorithme gourmand ?

A Algorithme gourmand divise récursivement un ensemble de ressources en fonction de la disponibilité immédiate maximale de cette ressource à chaque étape de l'exécution.

La résolution d'un problème par l'approche gloutonne comporte deux étapes :

1. Scanner la liste des éléments
2. Optimisation

Les deux étapes s'exécutent en parallèle, le tableau d'entrée étant progressivement divisé.

Pour suivre l'approche gloutonne, une bonne connaissance de la récursivité et du changement de contexte vous sera utile. trace le code. Le paradigme glouton peut être décrit par une paire d'énoncés nécessaires et suffisants.

Deux conditions définissent le paradigme gourmand.

• Chaque choix, étape par étape, doit orienter le problème vers sa solution la plus acceptable.
• La structure du problème doit s'arrêter en un nombre fini d'étapes gloutonnes.

La théorie étant posée, examinons l'histoire de l'approche de recherche gloutonne.

Histoire des gourmands Algorithms

Voici les jalons importants de l'histoire des algorithmes gloutons :

• Les algorithmes gloutons ont été conceptualisés pour la première fois dans les années 1950 pour les algorithmes de parcours de graphes.
• Edsger Dijkstra a développé son algorithme de chemin le plus court pour raccourcir les itinéraires à travers la capitale néerlandaise, Amsterdam.
• Au cours de la même décennie, Prim et Kruskal ont développé des stratégies d'optimisation qui minimisent les coûts des chemins le long d'itinéraires pondérés pour construire des arbres couvrants minimaux.
• Dans les années 70, les chercheurs américains Cormen, Leiserson, Rivest et Stein ont décrit la sous-structuration récursive des solutions gloutonnes dans leur ouvrage classique Introduction to Algorithms cahier de texte.
• Le paradigme de recherche gloutonne a été répertorié comme une stratégie d'optimisation distincte dans les archives du NIST en 2005.
• Aujourd'hui encore, des protocoles web tels que Open Shortest Path First (OSPF) et de nombreux protocoles de commutation de paquets utilisent la stratégie gloutonne pour minimiser le temps de transit sur un réseau.

Stratégies et décisions avides

La logique se réduit à un choix binaire à chaque étape — « gourmand » ou « non gourmand » — en fonction de la direction que prend l'algorithme pour progresser.

Par exemple, l'algorithme de Dijkstra identifie les hôtes sur Internet en évaluant une fonction de coût à chaque étape. La valeur renvoyée par cette fonction détermine si le chemin suivant est « glouton » ou « non glouton ».

En bref, un algorithme cesse d'être gourmand dès l'instant où il effectue une étape qui n'est pas localement optimale, et les problèmes gourmands s'arrêtent lorsqu'aucune autre étape gourmande n'est possible.

Caractéristiques de l'algorithme gourmand

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

• Une liste ordonnée de ressources comporte des attributions de coût ou de valeur qui quantifient les contraintes du système.
• L'algorithme utilise la quantité maximale de ressources dans le temps imparti.
• Par exemple, dans un problème de planification d'activités, les coûts des ressources sont mesurés en heures et les activités doivent être réalisées en série.

Pourquoi utiliser l'approche gourmande ?

Voici les raisons d’utiliser l’approche gourmande :

• L'approche gourmande présente des compromis qui la rendent particulièrement adaptée à l'optimisation.
• La raison la plus évidente est de trouver immédiatement une solution réalisable. Dans le problème de sélection d'activités présenté ci-dessous, si plusieurs activités peuvent être planifiées avant la fin de l'activité en cours, elles peuvent l'être dans la même fenêtre temporelle.
• Une autre raison est qu'elle divise un problème de manière récursive en fonction d'une condition, sans qu'il soit nécessaire de fusionner les sous-solutions.
• Dans le problème de sélection d'activités, l'étape de division récursive est réalisée en parcourant la liste une seule fois et en ne considérant que les activités éligibles.

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

Dans l'exemple de planification des activités, chaque activité possède une heure de début et de fin et est identifiée par un numéro. Il existe deux catégories d'activités :

1. Activité envisagée : l'activité de référence à partir de laquelle on mesure la capacité à intégrer d'autres activités restantes.
2. Activités restantes : activités à un ou plusieurs indices en avance sur l’activité considérée.

Le coût d'exécution d'une activité est sa durée, calculée comme (fin – début).

L'étendue gourmande correspond simplement au nombre d'activités restantes qui peuvent être réalisées dans le temps imparti à une activité considérée.

Architecture de l’approche gourmande

Étape 1) Examinez la liste des coûts d'activité en commençant par l'indice 0 comme indice de référence.

Étape 2) Si d'autres activités peuvent se terminer avant la fin de l'activité considérée, recherchez ces activités restantes.

Étape 3) Si aucune autre activité ne peut être planifiée, l'activité restante est prise en compte. Répétez les étapes 1 et 2 avec cette nouvelle activité. S'il ne reste plus d'activités, passez à l'étape 4.

Étape 4) Renvoyer l'union des indices considérés — ce sont les indices d'activité qui maximisent le débit.

Architecture de l’approche gourmande

Code Explication

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

#define MAX_ACTIVITIES 12

Explication du code:

1. Fichiers/classes d'en-tête inclus
2. Le nombre maximal d'activités configurables par l'utilisateur.

using namespace std;

class TIME
{
    public:
    int hours;

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

Explication du code:

1. Déclare l'espace de noms standard pour les opérations de flux.
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. Définition de classe pour Activity.
2. Horodatages qui, ensemble, définissent une durée.
3. Dans le constructeur par défaut, tous les horodatages sont initialisés à 0.

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. considered_index est le point de départ de l'analyse du tableau.
3. init_index est utilisé pour attribuer des horodatages aléatoires lors de la configuration.
4. Un tableau d'objets Activity est alloué dynamiquement avec l'opérateur new.
5. Le pointeur programmé contient le résultat glouton actuel.

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

Explication du code:

1. Le constructeur Scheduler — deuxième partie de la définition de la classe.
2. considered_index marque le début de l'analyse en cours.
3. L'étendue de la gourmandise est indé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);
 }
&#8230;
&#8230;

Explication du code:

1. Une boucle « for » initialise les heures de début et de fin de chaque activité programmée.
2. Initialise l'heure de début.
3. Initialise l'heure de fin à l'heure de début ou après.
4. Une instruction de débogage affiche 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 Scheduler.
2. activity_select() prend un index de départ comme base et divise la quête gourmande en sous-problèmes.

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

1. L'opérateur de résolution de portée (::) relie la définition de la fonction à la classe Scheduler.
2. L'index considéré est passé par valeur, et l'étendue gourmande est initialisée à l'index qui le suit immédiatement.

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;
...

Explication du code:

1. La logique de base — l'étendue gourmande est plafonnée à MAX_ACTIVITIES.
2. L'heure de début de l'activité en cours est comparée à l'heure de fin de l'activité considérée.
3. Tant que la condition est remplie, un message de débogage optionnel est affiché.
4. L'étendue gourmande passe ensuite à l'index suivant dans le tableau d'activités.

...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

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

Explication du code:

1. La condition vérifie si toutes les activités ont été couvertes.
2. Sinon, l'algorithme relance la recherche gourmande à partir de l'index actuel — une étape récursive qui divise le problème de manière gourmande.
3. Si oui, le contrôle est rendu à l'appelant sans possibilité d'étendre sa 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 invoque le planificateur.
2. Un nouvel objet Scheduler est instancié.
3. La fonction activity_select() renvoie un pointeur Activity à 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

L'approche gloutonne n'est pas adaptée aux problèmes qui nécessitent une solution optimale pour chaque sous-problème, comme le tri.

Dans de tels cas, la méthode gloutonne peut être erronée — dans le pire des cas, elle produit une solution non optimale.

Le principal inconvénient des algorithmes gloutons est qu'ils choisissent sans savoir ce qui se trouve après l'état glouton actuel.

Le schéma ci-dessous illustre cet inconvénient de la méthode gourmande.

Dans l'analyse gourmande représentée ici sous forme d'arbre (une valeur plus élevée signifie une plus grande gourmandise), un algorithme à la valeur 40 choisirait 29 ensuite, puis s'arrêterait à 12, pour un total de 41.

En revanche, une stratégie de diviser pour régner suivrait 25 avec 40 pour un total de 65, ce qui est 24 points de plus que le choix localement gourmand.

Exemples de gourmands Algorithms

La plupart des algorithmes de réseau reposent sur une approche gloutonne. Voici quelques exemples courants d'algorithmes gloutons :

• Algorithme de l'arbre couvrant minimal de Prim
• Problème du voyageur de commerce (approximatif)
• Coloration de cartes graphiques
• Algorithme de Kruskal pour l'arbre couvrant minimal
• Algorithme de Dijkstra pour le plus court chemin
• Couverture de sommets du graphe
• Problème de sac à dos
• Ordonnancement des tâches avec échéances

FAQ