Le Livre d'or • avoir tout Vikidia hors-connexion
Problème du sac à dos
Le problème du sac à dos est un problème informatique d'optimisation. Il consiste à chercher, étant donné un sac supportant une masse donnée et différents objets ayant une masse et une valeur variables, quelle combinaison d'objets il est le plus rentable d'emporter dans le sac à dos.
Présentation[modifier | modifier le wikicode]
Arsène, un cambrioleur, vient de pénétrer dans une maison pour y voler des objets de valeur. Il a devant lui 1 kg de chocolat, qui vaut 10 €, une encyclopédie qui pèse 5 kg et qui vaut 35 € et un vieil ordinateur pesant 2 kg et valant 30 €. Seulement, son sac de cambrioleur ne supporte pas une masse de plus de 6 kg. Quels objets devrait-il choisir pour voler le plus d'argent ?
Ce problème a l'air simple en apparence, mais il ne l'est pas : pour un grand nombre d'objets, il devient difficile de trouver l'ensemble d'éléments qu'il est le plus rentable d'emporter. De même que le problème du voyageur de commerce, le problème du sac à dos est NP-complet : on peut facilement vérifier qu'un ensemble d'objets est la bonne solution, mais on ne peut pas déterminer facilement cet ensemble d'objets. 1
Pour le modéliser plus formellement, on peut noter qu'un objet i possède un poids pi et une valeur vi. Résoudre le problème revient alors à trouver les objets (numérotés de 1 à n) vérifiant p1 + p2 + p3 + ... + pn inférieur ou égal au poids maximal supporté par le sac, avec en même temps v1 + v2 + v3 + ... + vn le plus grand possible.
Méthodes de résolution[modifier | modifier le wikicode]
Comme c'est souvent le cas pour les problèmes NP-complets, la difficulté à trouver une solution exacte a conduit au développement de méthodes approchées, aussi appelées heuristiques. Nous allons voir ces deux approches.
Méthodes approchées[modifier | modifier le wikicode]
Ce problème peut se résoudre de manière approchée à l'aide d'un algorithme d'un type particulier : un algorithme glouton. Il s'agit d'un algorithme qui, lorsqu'on lui demande de faire un choix (entre des parts de gâteau, entre deux routes , etc.), choisit toujours la solution la plus avantageuse à l'instant t, sans jamais remettre en question ses choix par la suite. On dit qu'il fait à chaque étape un choix localement optimal. Pour le problème qui nous intéresse, on pourrait tout d'abord imaginer un algorithme glouton qui privilégie les objets de plus grande valeur. Il y a cependant des situations où ce type d'approche n'est pas très efficace.
Considérer uniquement les valeurs des objets n'est donc pas pertinent, il faut aussi tenir compte de leur poids. On peut donc imaginer cette fois-ci un alogorithme glouton qui calcule pour chaque objet i le rapport entre sa valeur vi et son poids pi, et privilégier les objets qui ont les plus grands . Un algorithme glouton ressemblerait alors à :
Fonction glouton (n = nombre d'objets, poids_max = poids maximal que le sac à dos peut supporter) rapport_valeur_poids := [] Pour i allant de 1 à n avec un pas de 1 rapport_objet_i = valeur(i) / poids(i) Ajouter rapport_objet_i à rapport_valeur_poids fin Pour Trier l'ensemble des objet_i par rapport_objet_i décroissant poids_sac_a_dos = 0 liste_objets_sac = [] i := 1 Tant que poids_sac_a_dos < poids_max faire Si poids_sac_a_dos + poids(i) <= poids_max alors Ajouter objet_i à liste_objets_sac poids_max := poids_max + poids(i) fin Si i := i + 1 fin Tant que Renvoyer liste_objets_sac Fin Fonction
Cet algorithme a des performances variables selon l'ensemble d'objets utilisé. Si l'on reprend l'exemple la situation d'Arsène le cambrioleur, le glouton aurait calculé que l'encyclopédie, d'un poids de 5 pour une valeur de 35, n'était pas prioritaire par rapport aux autres objets. On peut représenter les rapports valeur / poids de chacun des objets dans un tableau pour le voir plus facilement :
Ordinateur | Chocolat | Encyclopédie |
---|---|---|
30/2 = 15 | 10/1 = 10 | 35/5 = 7 |
Le glouton aurait donc choisi comme objets l'ordinateur et le chocolat, alors que ce n'était pas le meilleur choix. Toutefois, il existe des situations où les algorithmes gloutons sont très efficaces. Par exemple, dans une variante du problème du sac à dos où l'on peut choisir de prendre des fractions d'objet (on peut décider de ne pas prendre un kilo entier de chocolat, mais de prendre seulement six carreaux de la tablette) 2, l'algorithme glouton est optimal, c'est-à-dire qu'il renverra toujours la meilleure solution. 3
Méthodes exactes[modifier | modifier le wikicode]
Les méthodes exactes vont généralement consister à calculer toutes les possibilités de remplissage du sac, pour ne conserver que celles qui maximisent la valeur totale du contenu du sac. On va s'aider d'un type particulier de graphe, qui s'appelle un arbre binaire. À chaque objet i on va associer un nombre tel que si l'objet i est dans le sac, vaut 1, et si l'objet i n'est pas dans le sac, vaut 0. L'arbre binaire va alors nous aider à détailler toutes les solutions possibles.
![](https://upload.wikimedia.org/wikipedia/commons/thumb/0/0a/Boretti_Arbre_niveau.png/400px-Boretti_Arbre_niveau.png)
Dans ce type de graphe, les cercles sont appelés nœuds, et correspondent à un embranchement. Le nœud tout en haut s'appelle la racine. Un chemin qui part de la racine et descend dans l'arbre s'appelle une branche. Les nœuds sont reliés entre eux par des arêtes, les segments. La profondeur k d'un nœud correspond au nombre d'arêtes qu'il faut parcourir pour remonter de ce nœud à la racine. Enfin, on appelle feuille un nœud tout en bas de l'arbre.
![](https://upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Arbre_binaire_exploration.svg/langfr-400px-Arbre_binaire_exploration.svg.png)
À chaque fois qu'on est à un nœud à une profondeur k, on va choisir si l'on met ou pas dans le sac l'objet k. Si on décide de le mettre dans le sac, prend comme valeur 1 et on descend à gauche. Si on décide au contraire de ne pas prendre l'objet, vaut 0 et on descend à droite. Le nœud représente donc un embranchement qui va traduire le choix de mettre ou non l'objet dans le sac. Une tentative de remplissage du sac est donc représentée par une branche de l'arbre allant jusqu'à une feuille (la branche en entier donc, de la racine jusqu'au bout de l'arbre). Les directions gauche-droite empruntées successivement représentent alors le fait que les objets à la profondeur associée aient été mis dans le sac ou non. Par exemple, si dans une branche, on passe successivement à gauche, à gauche, à droite puis à gauche, cela traduit le fait que le premier objet a été mis dans le sac, le deuxième aussi, le troisième non et le quatrième oui. On peut ainsi dénombrer toutes les combinaisons d'objets possibles. 4 À présent qu'on connaît toutes les possibilités, il faut regarder pour chacune d'elles si elle respecte la masse maximale d'objets dans le sac (si ce n'est pas le cas, cette solution est impossible, il faut donc l'exclure). Il faut ensuite calculer pour les solutions restantes lesquelles ont la plus grande valeur totale.
Applications[modifier | modifier le wikicode]
Le problème du sac à dos est utilisé pour la découpe de matériaux pour limiter les pertes, pour optimiser les chargements de cargaisons dans les avions, bateaux , etc. De manière plus inattendue, on le retrouve également en cryptographie, en étant à l'origine du premier algorithme de chiffrement asymétrique en 1976. Il est également utilisé en finance, pour maximiser les profits en choisissant les bons projets dans lesquels investir étant donné un montant d'investissement.
Voir aussi[modifier | modifier le wikicode]
- Problème du voyageur de commerce
- Problème NP-complet
- Mathématiques discrètes
- Graphe (théorie des graphes)
Notes et références[modifier | modifier le wikicode]
- ↑ Plus précisément, le nombre de calculs à faire pour déterminer la solution croît exponentiellement lorsque le nombre d'objets augmente.
- ↑ Bien sûr, en général, voler un quart d'ordinateur ne sert pas à grand-chose
- ↑ Numérique et Sciences Informatiques - Première, p. 322, S. Bays
- ↑ Pour n objets, il y a possibilités, soit répété n fois (on répète n fois la multiplication de 2 par lui-même)
Liens externes[modifier | modifier le wikicode]
- Article d' Interstices sur le problème du sac à dos, avec jeu interactif
- Problème du sac à dos sur Wikipédia
- (en) The Knapsack problem, sur Wikipedia
- Numérique et Sciences Informatiques - Première, p. 322-324, S. Bays, 2019, éditions Ellipses
|
|
|