Algorithmes gloutons

Sommaire du document

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 (scheduler[1] 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".

 

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≠ {} ∧ ∀ie,Il n'existe pas de je | i=jr initialisé
post-condition : epre=epost ∧ ∀ s=∑{ei,...en} #x ⇒ Il n'existe pas de{ej,...ek} #y | y<x[2]


Code (Pseudo-code de retourMonnaie) (7 lignes) :
  1. fonction retourMonnaie(s: Entier, e: Liste<Entier>, r: Liste<Entier>) : Liste<Entier>
  2. si s=0
  3. Entier x=la plus grande valeur infé;rieure ou é;gale à; s
  4. r = cons(x, r)
  5. 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}.

 

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 élaguons[3] 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.

 

Réseaux sociaux

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher les interactions avec les réseaux sociaux sur ces pages.

 

Nuage de mots clés

4 mots clés dont 0 définis manuellement (plus d'information...).

Avertissement

Cette page ne possède pas encore de mots clés manuels, ceci est donc un exemple automatique (les niveaux de pertinence sont fictifs, mais les liens sont valables). Pour tester le nuage avec une page qui contient des mots définis manuellement, vous pouvez cliquer ici.

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher le nuage de mots clés.

 

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.

 

Références

  1. livre Langue du document: fr IHDCB331 - Méthodes de Programmation : PY Schobbens, Cours de Méthodes de Programmation (Septembre 2009)
  2. livre Langue du document: uk Introduction to Algorithms : Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest (1999)

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.

 

Astuce pour imprimer les couleurs des cellules de tableaux : http://www.gaudry.be/ast-rf-450.html
Aucun commentaire pour cette page

© Ce document issu de l′infobrol est enregistré sous le certificat Cyber PrInterDeposit Digital Numbertection. Enregistrement IDDN n° 5329-11345
Document créé le 19/10/09 21:12, dernière modification le Vendredi 17 Juin 2011, 12:12
Source du document imprimé : http:///www.gaudry.be/programmer-algorithme-glouton.html
St.Gaudry©07.01.02
Outils (masquer)
||
Recherche (afficher)
Recherche :

Utilisateur (masquer)
Apparence (afficher)
Stats (afficher)
15838 documents
455 astuces.
550 niouzes.
3107 definitions.
447 membres.
8121 messages.

Document genere en :
0,09 seconde

Mises à jour :
Mises à jour du site
Citation (masquer)
Chuck Norris joue à World of Warcraft ET a une vie sociale.

Anonyme [Chuck Norris fact]
 
l'infobrol
Nous sommes le Mercredi 24 Mai 2017, 00:30, toutes les heures sont au format GMT+1.00 Heure, heure d'été (+1)