Algorithmes gloutons

Inhoudsopgave

Dans notre précédente approche de la programmation dynamique, et plus précisément la partie "diviser pour régner", nous divisions le problème en une série de problèmes plus simples, jusqu'au moment où la résolution du problème devient un cas de base, simple à effectuer. Ce type d'approche nous permet généralement de résoudre d'une manière optimale nos différents problèmes, mais il existe des problèmes pour lesquels une petite augmentation de la quantité de données à traiter mène rapidement la résolution du problème hors des capacités de nos machines, tant le nombre de possibilités devient important (par exemple le problème du voyageur de commerce).

Un cas d'algorithme glouton souvent utilisé est l'allocation de ressources (scheduler1 pour un processeur, salle de spectacle, création d'un horaire, etc.). Nous devons alors réguler l'accès aux ressources pendant un temps déterminé en respectant une série de contraintes.

Principe de l'algorithme glouton

Comme nous ne pouvons raisonnablement pas explorer toutes les solutions, nous allons procéder par choix heuristique. Comme un glouton qui cherche à avaler rapidement le plus posible, ou à réaliser le meilleur profit à court terme, nous allons présumer que le meilleur choix à court terme est le meilleur à long terme, et que l'ensemble des meilleurs choix à court terme nous ménera à une solution qui représente le meilleur choix dans sa totalité.

Nous constaterons cependant que ce n'est pas une constante, et qu'il est parfois préférable d'effectuer un choix qui semble mauvais à court terme (par exemple effectuer un investissement au lieu d'empocher un gain immédiat), mais qui conduit à un gain plus important à la fin. Pour cette raison, nous pouvons par exemple décider d'utiliser un algorithme glouton pour nous proposer rapidement une première solution qui serait de bonne qualité, et ensuite un type d'algorithme plus lent qui comparerait la solution avec d'autres. Nous utiliserons ce genre d'algorithme hybride lors de l'implémentation de paradigmes tels que "générer et tester" ou "branch and bound".

Inhoudsopgave Haut

L'algorithme glouton n'est pas optimal

Nous pouvons aisément démontrer que l'algorithme glouton ne nous fournit pas la meilleure solution par un contre-exemple: le problème du rendu de monnaie.

Soit e l'ensemble des monnaies. Le problème consiste à rendre une valeur s en utilisant le moins de pièces possible.

Selon le principe de l'algorithme glouton, nous utilisons le profit immédiat le plus important, donc la première pièce que nous rendons est celle qui a la plus grande valeur dans notre ensemble et dont la valeur ne dépasse pas la somme à rendre. Ensuite nous répétons l'opération sur une valeur plus simple (la somme à rendre, moins la pièce rendue) : nous avons donc un algorithme qui peut s'écrire de manière récursive.

Voici ce que cela peut donner en pseudo code :

fonction retourMonnaie(s: Entier, e: Liste<Entier>, r: Liste<Entier>)
s = somme à rendre
e = liste des monnaies possible
r = liste des monnaies déjà rendues
modifie : r
pré-condition : s: Entier initialisé ∧ e≠ {} ∧ ∀i ∈ e,Il n'existe pas de j ∈ e | i=j ∧ r initialisé
post-condition : epre=epost ∧ ∀ s=∑{ei,...en} #x ⇒ Il n'existe pas de{ej,...ek} #y | y<x2

  1. fonction retourMonnaie(s: Entier, e: Liste<Entier>, r: Liste<Entier>) : Liste<Entier>
  2. si s=0
  3. 	renvoyer r
  4. sinon
  5. 	Entier x=la plus grande valeur inférieure ou égale à s
  6. 	r = cons(x, r)
  7. 	renvoyer retourMonnaie(s-x, r)

Mauvais choix

Si nous exécutons ce code avec l'ensemble de monnaies {1, 4, 6, 7} pour nous rendre 10, il nous retourne l'ensemble de quatre pièces {7, 1, 1, 1} alors que la solution optimale est l'ensemble de deux pièces {6, 4}. Pour nous rendre 24, il nous retourne l'ensemble {7, 7, 7, 1, 1, 1} au lieu de l'ensemble {6, 6, 6, 6}

Avec l'ensemble de monnaies en euro cents {1, 2, 5, 10, 20, 50, 100, 200}, il semble nous donner toujours une solution optimale. Par exemple pour rendre 10 il retourne {10}, et pour 24 il retourne {20, 2, 2}.

Inhoudsopgave Haut

Critères de la stratégie gloutonne

Comme nous l'avons constaté lors de l'exemple du rendu de monnaie, le choix de l'ensemble de départ influence énormément le type de solution retournée. Nous devons veiller à avoir une sous-structure optimale, car une solution optimale d'un problème est la résolution de solutions optimales de problèmes similaires plus petits. Ce choix du sous-ensemble est un facteur qui nous indique si l'application d'un algorithme glouton à notre problème nous est bénéfique ou pas.

Un autre critère très important est le choix glouton à effectuer au niveau de notre sous-ensemble. En programmation gloutonne, nous effectuons le choix qui nous semble le plus opportun sur le moment, et puis nous résolvons les problèmes que ce choix implique. Nous élaguons3 une partie de l'arbre des solutions à chaque choix, alors que dans le cas de "diviser pour régner" le choix était fait pour chaque sous-ensemble.

Nederlandse vertaling

U hebt gevraagd om deze site in het Nederlands te bezoeken. Voor nu wordt alleen de interface vertaald, maar nog niet alle inhoud.

Als je me wilt helpen met vertalingen, is je bijdrage welkom. Het enige dat u hoeft te doen, is u op de site registreren en mij een bericht sturen waarin u wordt gevraagd om u toe te voegen aan de groep vertalers, zodat u de gewenste pagina's kunt vertalen. Een link onderaan elke vertaalde pagina geeft aan dat u de vertaler bent en heeft een link naar uw profiel.

Bij voorbaat dank.

Document heeft de 19/10/2009 gemaakt, de laatste keer de 16/07/2024 gewijzigd
Bron van het afgedrukte document:https://www.gaudry.be/nl/programmer-algorithme-glouton.html

De infobrol is een persoonlijke site waarvan de inhoud uitsluitend mijn verantwoordelijkheid is. De tekst is beschikbaar onder CreativeCommons-licentie (BY-NC-SA). Meer info op de gebruiksvoorwaarden en de auteur.

Notes
  1. ↑ Scheduler : Le scheduling (en français ordonnancement) est la répartition de tâches en fonction des ressources. Vous pouvez par exemple consulter les pages relatives à la gestion des processus par le scheduler.

  2. ↑ Post-condition : epre=epost ∧ ∀ s=∑{ei,...en} #x ⇒ Il n'existe pas de{ej,...ek} #y | y<x signifie "Pour tout ensemble de valeurs de e entre les bornes i et n (de nombre d'éléments x) dont la somme des valeurs correspond à la somme à rendre (s), il n'existe pas d'ensemble plus petit ensemble (de nombre d'éléments y) dont la somme corresponde à s"

  3. ↑ Pruning : Le pruning (élaguage en français) est surtout utilisé en "branch and bound" pour éviter d'explorer certaines branches de l'arbre des solutions.

Inhoudsopgave Haut

Referenties

  1. boek Taal van het document:fr IHDCB331 - Méthodes de Programmation : PY Schobbens, Cours de Méthodes de Programmation (September 2009)
  2. boek Taal van het document:uk Introduction to Algorithms : Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest (2000)

Deze verwijzingen en links verwijzen naar documenten die geraadpleegd zijn tijdens het schrijven van deze pagina, of die aanvullende informatie kunnen geven, maar de auteurs van deze bronnen kunnen niet verantwoordelijk worden gehouden voor de inhoud van deze pagina.
De auteur Deze site is als enige verantwoordelijk voor de manier waarop de verschillende concepten, en de vrijheden die met de referentiewerken worden genomen, hier worden gepresenteerd. Vergeet niet dat u meerdere broninformatie moet doorgeven om het risico op fouten te verkleinen.

Inhoudsopgave Haut