Fiche de révision : Algorithmes gloutons

Caractéristiques des algorithmes gloutons

Principe général

• Les algorithmes gloutons sont conçus pour prendre le maximum de ce qui est disponible à un moment donné et choisissent la solution optimale àchaque instant.
• La répétition de cette stratégie très simple, permet de résoudre rapidement et de manière souvent satisfaisante des problèmes d’optimisation sans avoir à tester systématiquement toutes les possibilités.
• Cependant un algorithme glouton ne fournit pas toujours le meilleur résultat possible.

Relativité de l’optimisation

• La solution obtenue par un algorithme glouton est le résultat d’une suite de choix gloutons, sans prise en compte des choix passés, ni anticipation de choix futurs.
• L’optimisation est potentiellement moindre qu’un algorithme effectuant une exploration systématique de toutes les possibilités.
• Les algorithmes gloutons sont capables de produire rapidement des résultats qui s’avèrent, dans de nombreux cas, suffisamment optimisés pour être acceptables.
• Les algorithmes gloutons sont souvent employés pour résoudre des problèmes d’optimisation, comme par exemple déterminer le plus court chemin dans un réseau ou encore compresser des données.

Rendu de monnaie

Énoncé du problème

• L’outil de rendu de monnaie pourra être intégré à un automate distributeur ou à une caisse enregistreuse afin de proposer un rendu de monnaie, permettant de préserver le fonds de caisse.
• Il faut conserver une monnaie suffisante dans notre fonds de caisse, et ainsi pouvoir continuer à rendre la monnaie le plus longtemps possible.

Stratégie gloutonne

• Consiste à rendre à chaque fois les plus gros billets ou les plus grosses pièces possibles, dans la plus grande quantité possible.
• Nous devons donc déterminer pour tout montant quel est le plus gros billet ou la plus grosse pièce qu’il est possible de rendre, et combien on peut en donner sans dépasser le montant restant à rendre.

Implémentation

• Définir la monnaie triées par ordre croissant.
• Notre fonction comporte deux paramètres :
• le montant à rendre ;
• les valeurs faciales.
• Notre algorithme calcule pour chaque valeur faciale :
• la quantité maximale de chaque valeur faciale qu’il est possible de rendre avec une division entière et l’ajoute au nombre de pièces et de billets à rendre ;
• le nouveau reste. Il retourne le nombre de pièces et de billets à rendre.
• Notre fonction se contente de nous indiquer le nombre de billets ou de pièces à rendre, mais elle peut aussi retourner une liste de tuples contenant chacun la quantité et la valeur faciale des billets ou pièces à rendre.

Problème du sac à dos

Énoncé du problème

• Nous disposons d’un sac à dos d’une contenance limitée. Nous avons à notre disposition différents types d’objets, de poids et de valeurs variables.
• Notre objectif est d’optimiser le chargement de notre sac sans dépasser le poids maximum autorisé par sa contenance.
• Il existe plusieurs versions du problème du sac à dos, mais dans notre cas d’étude nous allons travailler avec des objets fractionnables et dont la valeur par unité de poids peut différer d’un objet à l’autre.

Stratégie gloutonne

• Nous voulons emporter la valeur énergétique maximale dans la limite de la capacité du sac. Notre objectif est de pouvoir nous alimenter le plus longtemps possible.
• Notre stratégie gloutonne sera alors de toujours commencer par prendre l’aliment le plus dense énergétiquement, et dans la plus grande quantité possible, en partie ou en totalité, selon le poids encore admissible dans le sac.

Implémentation

• Notre implémentation retournera la valeur énergétique totale disponible dans le sac et les quantités prises pour chaque aliment.
• Nous devons lui communiquer en entrée :
• la capacité du sac à dos ;
• la quantité de chaque aliment sous forme de liste ;
• leur densité énergétique correspondante sous forme de liste également (non forcément ordonnée).
• L’aliment le plus énergétique possible est recherché à chaque fois. On évalue ensuite, s’il est possible de le prendre ou non en totalité. La quantité restante disponible est mise à jour en fonction de la quantité mise dans le sac. La capacité restante du sac est pareillement mise à jour à chaque tour de boucle.
• Notre algorithme glouton produit bien le résultat attendu, mais avec ses boucles imbriquées, sa complexité temporelle est $\text{O}(\text{n}^2)$.

Optimisation

• Nous allons générer un index spécifique qui fournira l’ordre dans lequel lire les densités et les quantités correspondantes, en nous basant sur des densités décroissantes.
• Pour construire notre index, nous mettrons à profit les possibilités de tri avec un critère personnalisé proposés optionnellement par la méthode sort().
• En intégrant ce tri personnalisé préalable, nous pouvons simplifier notre algorithme glouton.
• Nous avons supprimé l’imbrication de boucle, réduisant le coût cette partie de l’algorithme de $\text{O}(\text{n}^2)$ à $\text{O}(\text{n})$.
• La complexité de ce tri étant pseudo-linéaire, le coût temporel global de notre nouvel algorithme est donc $\text{O}(\text{n}\,\text{log}\,\text{n})$.