Dans ce document, on s'intéresse à une classe de problèmes d'optimisation connus sous le nom général de « problème du sac à dos ». On peut définir ce problème de la manière suivante : *« durant un cambriolage un voleur possède un sac dont la capacité (en poids par exemple) est limitée. Il se trouve face à un ensemble d'objets qu'il veut dérober. Chacun de ces objets est caractérisé par sa valeur et son poids. Le voleur souhaite optimiser la valeur totale des objets qu'il dérobe tout en ne dépassant pas le poids maximal supporté par son sac ».*
Ce problème est une abstraction pour un grand nombre d’autres problèmes d’optimisation. Il a été utilisé en cryptographie comme base pour différents schémas de chiffrement1. Il faut cependant noter que la plupart de ces schémas de chiffrement ne sont plus actuellement considérés comme sûrs. ^1, il est utilisé lors du chargement des bateaux ou d’avions, lors de la découpe de matériaux (minimisation des coupes « chutes » lors de la découpe), etc.
Problème étudié
On considère un sac à dos de masse maximale m=40kg dans lequel on souhaite ranger les objets dont les caractéristiques sont données ci-dessous :
Objet
A
B
C
D
E
F
Masse
13
12
8
10
14
18
Valeur
700
500
200
300
600
800
Quels objets faut-il sélectionner de façon à ce que la valeur totale, dans le sac à dos, soit maximale ?
Méthode de résolution approchée : stratégie gloutonne
Rappeler ce qu’est une stratégie gloutonne.
Réponse
À retenir
Les algorithmes gloutons forment une catégorie d’algorithmes permettant de parvenir à une solution pour un problème d’optimisation qui vise à maximiser/minimiser une quantité (plus court chemin (GPS), plus petite durée d’exécution, meilleure organisation d’un emploi du temps, etc.)
Le principe d’un algorithme glouton est le suivant :
Résoudre un problème étape par étape ;
À chaque étape, faire le choix optimal de moindre coût (de meilleur gain).
Le choix effectué à chaque étape n’est jamais remis en cause, ce qui fait que cette stratégie permet d’aboutir rapidement à une solution au problème de départ. C’est en ce sens que l’adjectif greedy (glouton/avare) caractérise cet algorithme : il se termine rapidement (glouton) sans fournir beaucoup d’efforts (avare).
Dans la partie principale du programme, définir la liste objets dont les membres sont des dictionnaires représentant les différents objets du problème.
Chacun de ces dictionnaires doit posséder les clés nom, masse, valeur associées aux valeurs.
Solution
Définir la variable masse_max et lui affecter la valeur 40.
Solution
masse_max=40
Le principe de la stratégie gloutonne consiste à ajouter en priorité les objets « les plus efficaces ». « Plus efficace » ne signifie pas « plus grande valeur » mais « plus grande valeur comparativement à la masse ».
Avant d’appliquer l’algorithme glouton, il est nécessaire de trier la liste objets. Définir la fonction suivante :
deftri_objets(objets:list[dict])->list[dict]:"""
Trie la liste de dictionnaires selon les rapports valeur/masse.
"""defrecupere_rapports(objet):returnobjet["valeur"]/objet["masse"]objets_tries=sorted(objets,key=recupere_rapports)returnobjets_tries
Quel concept propre à la programmation fonctionnelle la fonction sorted met-elle en œuvre ?
Solution
Une fonction en Python peut être passée comme argument à une autre fonction.
Décrire précisément la structure et le comportement de la fonction tri_objets.
Affecter, dans la fonction main, le résultat de l’appel de la fonction tri_objets à la variable objets.
Afficher à l’écran la liste triée.
Solution
Définir la fonction construction_sac_a_dos dont la spécification est :
defconstrution_sac_a_dos(objets_tries:list[dict],masse_max:float)->tuple[list[str],int,int]:"""
Construction du sac à dos à partir d'une stratégie gloutonne.
HYPOTHÈSE : la liste de dictionnaires est triée par ordre croissant des rapports
valeurs/masses.
Retourne un tuple constitué d'une liste contenant les noms des objets sélectionnés,
de la valeur du sac à dos et de la masse du sac à dos.
"""
Solution
defconstrution_sac_a_dos(objets_tries:list[dict],masse_max:float)->tuple[list[str],int,int]:"""
Construction du sac à dos à partir d'une stratégie gloultonne.
HYPOTHÈSE : la liste de dictionnaires est triée par ordre croissant des rapports
valeurs/masses.
Retourne un tuple constitué d'une liste contenant les noms des objets sélectionnés,
de la valeur du sac à dos et de la masse du sac à dos.
"""masse_sac=0valeur=0liste_objets=[]i=len(objets_tries)-1# Compteurwhilei>=0:objet=objets_tries[i]# objet est un dictionnaireif(masse_sac+objet["masse"])<=masse_max:valeur+=objet["valeur"]masse_sac+=objet["masse"]liste_objets.append(objet["nom"])i-=1# Décrémentation du compteurreturn(liste_objets,valeur,masse_sac)
Affecter, dans la partie principale du programme, le tuple retourné par la fonction construction_sac_a_dos aux variables sac_a_dos,valeur et masse_sac.
Solution
print("Stratégie gloutonne")print("-------------------")print(f"Constitution du sac à dos : {sac_a_dos}")print(f"Masse du sac à dos : {masse_sac}")print(f"Valeur du sac à dos : {valeur}")print()
Extension : Méthode de résolution exacte
Si on ne prend pas en compte, dans un premier temps, les contraintes, il est possible d’établir la liste des combinaisons possibles des objets à l’aide d’un arbre d’exploration binaire.
Par exemple, voici ce à quoi cet arbre ressemble lorsqu’on prend en compte les trois premiers objets :
graph TD
V("" ) --- A
V --- V1((" "))
A --- C(("A,B"))
C --- D(("A,B,C"))
C --- E(("A,B"))
A --- F(("A"))
F --- G(("A,C"))
F --- H(("A"))
V1 --- I(("B"))
I --- J(("B,C"))
I --- K(("B"))
V1 --- V2((" "))
V2 --- L(("C"))
V2 --- M((" "))
Les combinaisons s’obtiennent en parcourant l’arbre du sommet jusqu’à chaque extrémité : on obtient alors un vecteur dont on peut calculer la poids et la valeur. Il suffit alors de retenir celui dont la masse est inférieure à la masse maximale et dont la valeur est alors maximale.
Au niveau de chaque nœud à quoi correspond le chemin « gauche » : objet retenu ou objet non retenu ?
Réponse
Objet retenu.
Compléter l’arbre avec l’objet D.
Si on implémente un algorithme mettant en œuvre la technique présentée ici, on trouve comme solution [A,C,F]. Vérifier que cette solution est meilleure que celle donnée par l’algorithme glouton.
Pourquoi cette méthode n’est cependant pas utilisable la plupart du temps ? Quel est le nombre de combinaisons possibles ?
Réponse
Le nombre de combinaisons est 2n où n est le nombre d’objets. Cette croissance exponentielle rend l’algorithme exact beaucoup trop lent.
Écrire le code de la fonction masse_sac dont la spécification est :
defmasse_sac(objets:list[dict[str,str]],liste_obj:list[int])->int:"""
Calcule la masse du sac pour la liste d'objets retenus liste_obj.
"""
Écrire le code de la fonction calcul_valeur_sac dont la spécification est :
defcalcul_valeur_sac(objets:list[dict[str,str]],liste_obj:list[int])->int:"""
Calcule la masse du sac pour la liste d'objets retenus liste_obj.
"""
Écrire le code suivant :
defrecherche_recursive(objets:list[dict[str,str]],masse_max:isinstance,list_obj:list[int],i:int)->list[int]:"""
Détermine le chemin de l'arbre de décision correspondant à la valeur optimale
pour une masse du sac déterminée.
"""ifi==len(objets):returnlist_obj[:]val1=-1# Initialisation à une valeur impossible du poidsifobjets[i]["masse"]<=masse_max-masse_sac(objets,list_obj):# Ajoute objet si m_sac - m_inter > 0list_obj[i]=1sol1=recherche_recursive(objets,masse_max,list_obj,i+1)val1=calcul_valeur_sac(objets,sol1)list_obj[i]=0# On n'ajoute pas l'objetsol2=recherche_recursive(objets,masse_max,list_obj,i+1)val2=calcul_valeur_sac(objets,sol2)ifval1>val2:returnsol1[:]else:returnsol2[:]