Dans cette dernière partie sur les algorithmes, nous allons voir les algorithmes gloutons. On va commencer par un exemple : le problème du sac à dos. Puis on reviendra ensuite sur ce qu'est un algorithme glouton.
Les solutions, complètes ou partielles, des exercices sont en bas de page.
Introduction sur le problème du sac à dos
Ce problème s'énonce de la manière suivante :
j'ai un sac à dos dans lequel je ne peux pas dépasser un poids maximal PMAX
je peux mettre dedans des objets (caractérisés par leur valeur et leurs poids)
quels objets choisir pour avoir un sac à dos de valeur maximale ?
Dans notre exemple :
le sac à dos ne peut pas dépasser PMAX = 30 kg
objet 1 : poids 12 kg et valeur 7 €
objet 2 : poids 11 kg et valeur 4 €
objet 3 : poids 8 kg et valeur 3 €
objet 4 : poids 10 kg et valeur 3 €
Comment choisir les objets pour avoir la plus grande valeur possible dans le sac à dos ?
Test de toutes les possibilités
On appelle {} le contenu de notre sac à dos. {1} signifie qu'on a mis l'objet 1 dans notre sac à dos. L'image ci-dessus représente toutes les possibilités pour notre sac à dos, mais sans tenir compte du fait que notre sac à dos ne peut pas dépasser PMAX = 30 kg.
Exercice 1
Pour chaque possibilité, calculer le poids P du sac à dos.
Eliminer les possiblités qui ne vérifient pas la contrainte P ≤ PMAX.
Quelle est la valeur maximale que peut contenir le sac à dos ?
La valeur maximale trouvée correspond-t-elle à une possibilité unique ?
Exercice 2
On reprend le même sac à dos que dans l'exercice précédent :
Combien de possibilité a-t-on obtenu avant d'appliquer la contrainte sur notre sac à dos (c'est à dire avant de voir si le poids de notre sac à dos est inférieur ou égal à PMAX) ?
Quelle formule permet de trouver le nombre de possibilité si on a n objets ?
On considère l'algorithme qui choisit de parcourir l'arbre des solutions, puis de déterminer la contrainte (P ≤ PMAX). Quel sera le taux de croissance minimal de cet algorithme ?
A partir de combien d'objets, ce calcul devient-il infaisable par un ordinateur ?
On voit donc qu'il est impossible de résoudre ce problème pour un nombre d'objet assez restreint avec un tel algorithme. Chercher une solution exacte (ou optimale) à ce problème n'est pas tout le temps possible, que ce soit avec l'algorithme qui passe en revue toutes les possibilités ou un autre algorithme.
Solution approchée gloutonne
Peut-on faire autrement que lister toutes les possibilités et déterminer la meilleure ?
Exercice 3
Quel classement préliminaire (c'est à dire avant de choisir quoi mettre dans le sac à dos) peut-on faire ? Ce classement doit être lié à la valeur des objets puisque le sac à dos doit avoir la plus grande valeur possible; il doit aussi être lié à la contrainte que nous avons : le poids maximal du sac à dos. Quel classement obtenez-vous ?
En vous basant sur le classement de la réponse précédente, quelle solution obtenez-vous ? La représenter sous une forme d'arbre comme ci-dessus.
Cette solution est-elle optimale (c'est à dire la meilleure) ?
Exercice 4
On reprend l'exercice 3 précédent en modifiant le poids de l'objet 1 qui devient 13 kg au lieu de 12 kg.
Dans quel ordre classe-t-on les objets afin de faire un choix glouton ?
Quelle solution obtenez-vous ?
Si on refait l'exercice 1 avec ce nouveau jeu de données, on obtient l'arbre 1 ci-dessous. Cette solution est-elle optimale (c'est à dire la meilleure) ?
Est-ce que le choix glouton parcourt tout l'arbre des possibilités ? Si non, représenter sur l'arbre 2 le chemin suivi.
Exercice 4 : Arbre 1 des possibilitésExercice 4 : Arbre 2 des possibilités ré-écrit dans l'ordre glouton
Exercice 5
On ne considère que 2 objets :
objet 1 : poids : 1 kg et valeur : 2 €
objet 2 : poids 30 kg et valeur : 30 €
Le poids maximal du sac à dos est toujours de 30 kg.
Quelle est la plus grande valeur que peut avoir le sac à dos ?
Appliquer une stratégie gloutonne : à quel résultat arrivez-vous ?
Que peut-on en conclure sur l'utilisation d'une stratégie gloutonne ?
Conclusion
Un algorithme glouton est un algorithme qui fait le choix optimal (ou le meilleur choix possible)
localement (là où il est en train de calculer), sans avoir de vue d'ensemble.
Un algorithme glouton ne remet jamais en cause un choix fait précédemment.
On espère que ce choix localement bon donnera accès à une solution globalement optimale !
On a vu que c'était parfois le cas. Mais on a aussi vu que ce n'était pas tout le temps le cas.
Il n'y a pas de méthode pour construire une solution systématiquement optimale, de manière gloutonne,
dans tous les cas de figure, si on ne casse pas les objets.
Si on peut casser le dernier objet à mettre dans le sac à dos, alors l'approche gloutonne donne
systématiquement une solution globalement optimale.
Si on ne peut pas casser le dernier objet, alors la solution gloutonne ne sera pas forcément bonne.
Et on a vu que la solution gloutonne pouvait être très mauvaise.
Attention : ce qui est traître dans cette introduction, c'est que le nombre de possibilité étant
très petit, on a pu facilement construire l'arbre des possibilités (dont la taille est exponentielle
en fonction du nombre d'objet). Dans un cas plus réel, on ne serait pas capable de prédire
facilement dans quelle mesure la solution obtenue est optimale ou non.
