Algorithme gourmand avec exemples: méthode gourmande & Approcher

Table des matières:

Anonim

Qu'est-ce qu'un algorithme gourmand?

Dans Greedy Algorithm, un ensemble de ressources est divisé de manière récursive en fonction de la disponibilité maximale et immédiate de cette ressource à tout stade d'exécution donné.

Pour résoudre un problème basé sur l'approche gourmande, il y a deux étapes

  1. Analyse de la liste des éléments
  2. Optimisation

Ces étapes sont couvertes en parallèle dans ce tutoriel sur l'algorithme Greedy, en cours de division du tableau.

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.

Avec la poursuite de la théorisation, décrivons l'histoire associée à l'approche de recherche cupide.

Dans ce didacticiel sur l'algorithme Greedy, vous apprendrez:

  • Histoire des algorithmes gourmands
  • Stratégies et décisions gourmandes
  • Caractéristiques de l'approche gourmande
  • Pourquoi utiliser l'approche gourmande?
  • Comment résoudre le problème de sélection des activités
  • Architecture de l'approche gourmande
  • Inconvénients des algorithmes gourmands

Histoire des algorithmes gourmands

Voici un jalon important des algorithmes gourmands:

  • Des algorithmes gloutons ont été conceptualisés pour de nombreux algorithmes de parcours de graphes dans les années 1950.
  • Esdger Djikstra a conceptualisé l'algorithme pour générer des arborescences minimales. Il visait à raccourcir la durée des routes dans la capitale néerlandaise, Amsterdam.
  • Au cours de la même décennie, Prim et Kruskal ont réalisé des stratégies d'optimisation basées sur la minimisation des coûts de trajet le long des itinéraires pesés.
  • Dans les années 70, des chercheurs américains, Cormen, Rivest et Stein ont proposé une sous-structuration récursive de solutions gourmandes dans leur livre d'introduction classique aux algorithmes.
  • Le paradigme de recherche Greedy a été enregistré comme un type différent de stratégie d'optimisation dans les archives du NIST en 2005.
  • Jusqu'à ce jour, les protocoles qui exécutent le Web, tels que l'Open-shortest-path-first (OSPF) 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 gourmandes

La logique dans sa forme la plus simple se résumait à «gourmand» ou «pas gourmand». Ces énoncés ont été définis par l'approche adoptée pour avancer à 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étermine si le chemin suivant est "gourmand" ou "non gourmand".

Bref, un algorithme cesse d'être gourmand si à un stade quelconque il franchit une étape qui n'est pas localement gourmand. Les problèmes avides s'arrêtent sans autre étendue de cupidité.

Caractéristiques de l'approche gourmande

Les caractéristiques importantes d'un algorithme de méthode Greedy sont:

  • Il existe une liste ordonnée de ressources, avec des coûts ou des attributions de valeur. Celles-ci quantifient les contraintes sur un système.
  • Vous utiliserez la quantité maximale de ressources pendant le temps qu'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 l'ordre de série.

Pourquoi utiliser l'approche gourmande?

Voici les raisons d'utiliser l'approche gourmande:

  • L'approche gourmande a quelques compromis, qui peuvent la rendre appropriée pour 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 des activités (expliqué ci-dessous), si d'autres 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 balayant une seule fois une liste d'éléments et en considérant certaines activités.

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

Dans l'exemple de planification d'activités, il existe 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é de faire plus d'une activité restante est analysée.
  2. activités restantes: activités à un ou plusieurs index avant l'activité considérée.

La durée totale donne le coût de réalisation de l'activité. C'est-à-dire que (fin - début) nous donne la durée comme le coût d'une activité.

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

Architecture de l'approche gourmande

É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 actuelle devient la prochaine activité considérée. Répétez les étapes 1 et 2, avec la nouvelle activité considérée. S'il ne reste plus aucune activité, 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.

Architecture de l'approche gourmande

Explication du code

#include#include#include#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. Horodatage d'une heure.
  4. Un constructeur par défaut TIME
  5. La variable des heures.
class Activity{public:int index;TIME start;TIME finish;public: Activity(){start = finish = TIME();}};

Explication du code:

  1. Une définition de classe 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 de la matrice.
  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 du nouvel opérateur.
  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 de l'analyse en cours.
  3. L'étendue gourmande actuelle n'est pas définie au début.
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 planifiées.
  2. Début de l'initialisation de l'heure.
  3. L'initialisation de l'heure de fin est toujours postérieure ou exacte à 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'Index considéré est l'Index appelé par valeur. Le greedy_extent est un index initialisé juste 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 programmables avant que l'activité considérée (donnée par l'index considéré) ne se termine.
  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 courant. Il s'agit d'une étape récursive qui divise avidement l'énoncé du problème.
  3. Si oui, il retourne à l'appelant sans 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.

Production:

START:7 END 7START:9 END 10START:5 END 6START:10 END 10START:9 END 10Schedule start:5finish6activity:3Schedule start:9finish10activity:5

Inconvénients des algorithmes gourmands

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 de pratique d'algorithme Greedy, la méthode Greedy peut être erronée; dans le pire des cas, même conduire à une solution non optimale.

Par conséquent, l'inconvénient des algorithmes gourmands est de ne pas savoir ce qui précède l'état gourmand actuel.

Vous trouverez ci-dessous une description de l'inconvénient de la méthode Greedy:

Dans l'analyse gourmande représentée ici sous forme d'arbre (valeur plus élevée, plus grande cupidité), 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 a emprunté un chemin sous-optimal ou a adopté une stratégie de conquête. puis 25 seraient suivis de 40, et l'amélioration globale des coûts serait de 65, ce qui est évalué à 24 points de plus en tant que décision sous-optimale.

Exemples d'algorithmes gourmands

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

  • Algorithme d'arbre couvrant minimal de Prim
  • Problème de vendeur itinérant
  • Graphique - Coloration de la carte
  • Algorithme d'arbre couvrant minimal de Kruskal
  • Algorithme de Spanning Tree minimal de Dijkstra
  • Graphique - Couverture de sommet
  • Problème de sac à dos
  • Problème de planification des travaux

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 comme l'algorithme Greedy Python, C, C #, PHP, Java, etc. approcher. En fin de compte, les inconvénients de l'utilisation de l'approche gourmande ont été expliqués.