23 Cours Algorithmes gloutons
Le problème du sac à dos⚓︎
Durant un cambriolage, un voleur possède un sac dont la capacité (en masse par exemple) est limitée. Il se trouve face à un ensemble d’objets qu’il peut dérober. Chacun de ces objets est caractérisé par sa valeur et sa masse. Le voleur souhaite optimiser la valeur totale des objets qu’il va dérober tout en ne dépassant pas la masse maximale supportée par son sac.
Admettons que le cambrioleur ait à sa disposition les objets suivants et que la masse maximale supportée par son sac soit de \(30\) kg.
| Objet | \(A\) | \(B\) | \(C\) | \(D\) | \(E\) | \(F\) |
|---|---|---|---|---|---|---|
| Valeur (en euros) | \(700\) | \(400\) | \(300\) | \(300\) | \(500\) | \(200\) |
| Masse (en kg) | \(13\) | \(12\) | \(6\) | \(10\) | \(12\) | \(14\) |
Cas général : variante entière ou « tout ou rien » ou encore « 0/1 »⚓︎
Dans le cas le plus courant, le voleur ne peut sélectionner qu’un nombre entier d’objets.
Variante fractionnaire⚓︎
Il existe une variante du problème qui consiste à considérer que les objets sont fractionnables. Le voleur a, dans ce cas, la possibilité de ne prendre qu’une fraction du dernier objet dont il a besoin pour pouvoir remplir son sac au maximum.
Résolution du problème « à la main »⚓︎
Tri par valeurs décroissantes⚓︎
Imaginons que le voleur décide de mettre les objets dans le sac par ordre décroissant de leur valeur, tant qu'il y a de la place.
On trie les objets dans l'ordre décroissant de leurs valeurs :
| Objet | \(A\) | \(E\) | \(B\) | \(C\) | \(D\) | \(F\) |
|---|---|---|---|---|---|---|
| Valeur (en euros) | \(700\) | \(500\) | \(400\) | \(300\) | \(300\) | \(200\) |
| Masse (en kg) | \(13\) | \(12\) | \(12\) | \(6\) | \(10\) | \(14\) |
Puis on les sélectionne pour les mettre dans le sac :
| Objet | Valeur | Masse | Masse restante dans le sac |
|---|---|---|---|
| \(A\) | \(700\) | 13 | \(30 - 13=17\) |
| \(E\) | \(500\) | 12 | \(17 - 12=5\) |
On remarque que le voleur ne peut pas prendre d'autres objets car leurs masses dépassent la masse restante. On s’arrête donc à cette étape. En faisant la somme des valeurs, on obtient un total de \(700 + 500 = 1~200\) euros.
On a l'impression d'avoir gâché de la place, donc on étudie une autre option :
Tri par masses croissantes⚓︎
| Objet | \(C\) | \(D\) | \(E\) | \(B\) | \(A\) | \(F\) |
|---|---|---|---|---|---|---|
| Valeur (en euros) | \(300\) | \(300\) | \(500\) | \(400\) | \(700\) | \(200\) |
| Masse (en kg) | \(6\) | \(10\) | \(12\) | \(12\) | \(13\) | \(14\) |
À l’aide du tableau suivant, calculer la valeur totale contenue dans le sac du voleur dans ce cas.
| Objet | Valeur | Masse | Masse restante dans le sac |
|---|---|---|---|
| \(\phantom{700\times\frac34=\frac{2~100}{4}=525}\) | |||
Réponse
| Objet | Valeur | Masse | Masse restante dans le sac |
|---|---|---|---|
| \(C\) | \(300\) | \(6\) | \(30 - 6 = 24\) |
| \(D\) | \(300\) | \(10\) | \(24 - 10 = 14\) |
| \(E\) | \(500\) | \(12\) | \(14 - 12 = 2\) |
Il reste \(2\) kg de libres dans le sac, mais il n'y a pas d'objet qui y tienne.
La valeur de ce sac est de \(300 + 300 + 500 = 1~100\) euros. On a mis plus d'objets, mais ils valaient moins...
Tri par rapports « valeur/poids » décroissants⚓︎
| Objet | \(A\) | \(B\) | \(C\) | \(D\) | \(E\) | \(F\) |
|---|---|---|---|---|---|---|
| Valeur (en euros) | \(700\) | \(400\) | \(300\) | \(300\) | \(500\) | \(200\) |
| Masse (en kg) | \(13\) | \(12\) | \(6\) | \(10\) | \(12\) | \(14\) |
| Valeur / Masse | \(53,85\) | \(33,33\) | \(50\) | \(30\) | \(41,67\) | \(14,29\) |
À l’aide du tableau suivant, calculer la valeur totale contenue dans le sac du voleur dans ce cas.
| Objet | Valeur | Masse | Masse restante dans le sac |
|---|---|---|---|
| \(\phantom{700\times\frac34=\frac{2~100}{4}=525}\) | |||
Réponse
| Objet | Valeur | Masse | Masse restante dans le sac |
|---|---|---|---|
| \(A\) | \(700\) | \(13\) | \(30 - 13 = 17\) |
| \(C\) | \(300\) | \(6\) | \(17 - 6 = 11\) |
| \(E\) | ne rentre pas | ||
| \(B\) | ne rentre pas | ||
| \(D\) | \(300\) | \(10\) | \(11 - 10 = 1\) |
Il reste \(1\) kg de libre dans le sac, mais il n'y a pas d'objet qui y tienne.
La valeur de ce sac est de \(700 + 300 + 300 = 1~300\) euros. On a davantage optimisé le sac.
Variante fractionnaire du tri par rapports décroissants⚓︎
Le voleur peut, cette fois-ci, fractionner le dernier objet.
À l’aide du tableau suivant, calculer la valeur totale contenue dans le sac du voleur dans ce cas.
| Objet | Valeur | Masse | Masse restante dans le sac |
|---|---|---|---|
| \(\phantom{700\times\frac34=\frac{2~100}{4}=525}\) | |||
Réponse
| Objet | Valeur | Masse | Masse restante dans le sac |
|---|---|---|---|
| \(A\) | \(700\) | \(13\) | \(30 - 13 = 17\) |
| \(C\) | \(300\) | \(6\) | \(17 - 6 = 11\) |
| \(E\) | \(11 / 12^\text{e}\) des \(500\) euros | \(11 / 12^\text{e}\) des \(12\) kg | \(0\) |
| La valeur de ce sac est de \(700 + 300 + \dfrac{11}{12} \times 500 = 1458,33\) euros. |
Les solutions obtenues sont-elles optimales ? Pourrait-on faire mieux ?
Pour la variante fractionnaire, en remplissant par efficacité décroissante, on pourrait démontrer qu'on a optimisé la place disponible.
En revanche, pour le cas entier, c'est plus compliqué...
Il reste souvent de la place "gâchée", et il est alors difficile de justifier si on aurait pu faire mieux ou non...
Recherche du maximum⚓︎
Pour rechercher le maximum, et être sûr de notre optimisation, on pourrait :
- énumérer toutes les combinaisons possibles d'objets
- calculer la valeur dans chaque cas
- garder le maximum
On appelle cela l'exploration systématique ou la force brute.
La complexité d’une telle démarche est exponentielle (il s’agit, en effet, de considérer tous les sous-ensembles d’un ensemble d’objets). Nous serions en mesure de le faire pour l'exemple ci-dessus avec \(6\) objets, mais pour un grand nombre d'objets, cela deviendrait vite irréalisable.
Une autre approche consiste à utiliser un algorithme glouton (greedy en anglais) : il s’agit de faire une succession de choix en choisissant localement la solution optimale, sans retour en arrière. On progresse ainsi de façon descendante : on choisit une solution puis on résout un problème plus petit. C’est cette méthode que nous avons utilisée pour résoudre notre problème.
C'est ce que l'on fait quand on se déplace sur des chemins avec une boussole : par exemple, je sais que ma destination est au Nord, donc à chaque fois que je suis face à un embranchement, je choisis le chemin qui semble le plus se diriger vers le Nord. Je n'ai pas de garantie que ce sera le plus court chemin.
Les algorithmes gloutons⚓︎
Le problème du sac à dos trouve des applications pour la découpe de matériaux (afin de minimiser les pertes dues aux chutes), dans le chargement de cargaisons (bagages dans les avions, camions, bateaux). Le critère limitant peut être la masse, ou le volume...
Il fait partie d’un ensemble de problèmes dits d’optimisation combinatoire (il s’agit de choisir une meilleure alternative dans un ensemble fini mais très grand d’alternatives). On les rencontre dans de nombreux domaines (ingénierie, transports, logistique, robotique, intelligence artificielle, vie quotidienne, etc.).
En général, rien ne garantit que la solution obtenue soit optimale globalement. On parle alors d’heuristique gloutonne plutôt que d’algorithme glouton. C’est le cas, par exemple, de la variante entière de notre problème (voir exercice 2 de la fiche d'exercices). D’autres méthodes algorithmiques comme la programmation dynamique, que vous verrez en classe de Terminale, sont généralement plus adaptées à ce type de problème.
Sous certaines conditions cependant, on peut prouver que la solution obtenue est optimale. Par exemple, la solution au problème du sac à dos dans sa version fractionnaire obtenue par tri décroissant des rapports valeur/poids est optimale (on admettra cette proposition).