Aller au contenu

1NSI : TD Problème du Sac à Dos
& Algorithmes Gloutons⚓︎

Introduction⚓︎

  • Le but de ce TD est de présenter un problème classique, le Problème du Sac à Dos 🇫🇷 ou Knapsack Problem (KP) 🇺🇸,
  • et de le résoudre grâce à la méthode de programmation appelée Heuristique Gloutonne, c'est-à-dire que nous utiliserons des algorithmes gloutons.

Col

Image Sac à Dos

On dispose de plusieurs objets, ayant chacun:

  • un poids \(p_i\)
  • et une valeur \(v_i\) (par exemple en €)

On dispose d'un sac à dos qui supporte un poids maximal à ne pas dépasser \(P_{max}\).

Le problème du sac à dos consiste à remplir le sac à dos avec ces objets, de sorte que:

  • le poids final du sac à dos ainsi rempli, ne dépasse pas le poids maximal \(P_{max}\) supporté par le sac à dos
  • la somme totale de la valeur des objets placés dans le sac à dos soit maximale (la plus grande possible)

Def

\(\rightarrow\) Une solution sera dite possible lorsque la somme des poids des objets retenus est inférieure ou égale à \(P_{max}\)

\(\rightarrow\) La meilleure solution possible, i.e. celle dont la somme des valeurs \(v_i\) est la plus grande parmi toutes les solutions possibles, sera dite une solution optimale.

Animation Web⚓︎

Cette animation a été réalisée par Ouest INSA, à partir de l’applet réalisée dans le cadre d’un projet étudiant de l’École Polytechnique de l’Université de Tours, par Li Yifang, encadrée par Yannick Kergosien et Jean-Charles Billaut.

Un exemple débranché 🔌⚓︎

On se donne \(5\) objets et un sac à dos de poids maximal \(P_{max}=30\) kg

Objets A B C D E
Valeur \(v_i\) 11 6 8 15 7
Poids \(p_i\) 16 4 9 12 8

Notation : On note \(x\) une variable telle que, pour chaque objet \(i\):

  • \(x_i=1\) si on place l'objet \(i\) dans le sac à dos
  • \(x_i=0\) sinon

Débranché

Avec les notations précédentes:

  1. Traduisez sous forme d'une inégalité le fait que le poids total des objets retenus ne doit pas dépasser \(P_{max}\)
  2. Quelle somme doit être maximale?
  3. Déterminer manuellement (🔌) une solution optimale.

Heuristiques Gloutonnes pour le Problème du Sac à Dos⚓︎

On décide de résoudre ce problème avec une heuristique gloutonne. Le principe d’un Algorithme Glouton est de faire le meilleur choix pour prendre le premier objet, puis le meilleur choix pour prendre le deuxième, et ainsi de suite. Mais que faut-il entendre par meilleur choix ? On retrouve bien là toute la notion d'Heuristique, plusieurs heuristiques étant envisageables:

  • Heuristique 1 Est-ce prendre l’objet qui a la plus grande valeur?
  • Heuristique 2 l’objet qui a le plus petit poids?
  • Heuristique 3 l’objet qui a le rapport valeur/poids le plus grand ?
    Dans ce cas, on dit que l'objet est plus efficace.

Il faut encore départager ces \(3\) heuristiques.

Débranché

On reprend les 5 objets de l'Exercice précédent:

Objets A B C D E
Valeur \(v_i\) 11 6 8 15 7
Poids \(p_i\) 16 4 9 12 8

On décide de comparer les différentes heuristiques gloutonnes suivantes:

  1. Heuristique 1 On choisit à tout instant l'objet restant ayant le plus de valeur.

    Objets \(\,\) \(\,\) \(\,\) \(\,\) \(\,\)
    Valeur \(v_i\) \(\,\) \(\,\) \(\,\) \(\,\) \(\,\)
    Poids \(p_i\) \(\,\) \(\,\) \(\,\) \(\,\) \(\,\)

    • Objets retenus: _____________________________________________________________________________________
    • Poids : _____________________________________________________________________________________________
    • Valeurs : ___________________________________________________________________________________________

  2. Heuristique 2 On choisit à tout instant l'objet restant ayant le poids le plus faible.

    Objets \(\,\) \(\,\) \(\,\) \(\,\) \(\,\)
    Valeur \(v_i\) \(\,\) \(\,\) \(\,\) \(\,\) \(\,\)
    Poids \(p_i\) \(\,\) \(\,\) \(\,\) \(\,\) \(\,\)

    • Objets retenus: _____________________________________________________________________________________
    • Poids : _____________________________________________________________________________________________
    • Valeurs : ___________________________________________________________________________________________

  3. Heuristique 3 On choisit à tout instant l'objet restant le plus efficace, i.e. celui dont le rapport \(\,\, efficacité=\dfrac {valeur}{poids}\) est le plus grand

    Objets \(\,\) \(\,\) \(\,\) \(\,\) \(\,\)
    Valeur \(v_i\) \(\,\) \(\,\) \(\,\) \(\,\) \(\,\)
    Poids \(p_i\) \(\,\) \(\,\) \(\,\) \(\,\) \(\,\)

    • Objets retenus: _____________________________________________________________________________________
    • Poids : _____________________________________________________________________________________________
    • Valeurs : ___________________________________________________________________________________________

  4. Laquelle des 3 heuristiques précédentes vous semble être la meilleure dans le cas particulier de cet exemple?

  5. Comparez-les à la solution optimale de l'Exercice précédent. Que peut-on en déduire quant à l'optimalité d'un algorithme glouton?

Préparation de l'Algorithme Glouton

Nous verrons dans la prochaine partie que l'algorithme glouton fait la supposition que les données sont déjà triées, selon l'heuristique choisie. C'est le but de cet exercice: trier les données.

  1. En Python, Écrire une fonction efficacites(objets=[nom,v,p]:list)->[nom,v,p,eff]:list qui accepte en entrée une liste de listes objets=[nom,v,p] contenant:

    • la sous-liste des noms des objets,
    • la sous-liste de leurs valeurs v,
    • et la sous-liste de leurs poids p,

    et qui renvoie en sortie une liste des mêmes objets, augmentée de la sous-liste eff des efficacités, à calculer pour chaque objet.

  2. En Python, Écrire une fonction tri_insertion(objets=[nom,v,p,eff]:list,heuristique:str)->[nom,v,p,eff]:list qui accepte en entrée la liste de listes non triée objets=[nom,v,p,eff] contenant:

    • la sous-liste des noms des objets,
    • la sous-liste de leurs valeurs v,
    • la sous-liste de leurs poids p,
    • la sous-liste de leurs efficacités eff,
    • ainsi que l'heuristique:str choisie (parmi les 3 valeurs possibles: 'valeurs', 'poids' ou 'efficacite'),

    et renvoyant en sortie la liste de listes [nom,v,p,eff] triée par insertion selon l'heuristique choisie.

Principe de l'Algorithme Glouton pour le problème du Sac à Dos⚓︎

Notations de l'algorithme glouton⚓︎

  • n désigne le nombre d'objets
  • la liste objets=[noms,v,p,eff] contient plusieurs sous-listes:
    • la sous-liste noms des noms des n objets
    • la sous-liste v des valeurs des n objets
    • la sous-liste p des poids des n objets
    • la sous-liste eff des efficacités des n objets
  • On note x la liste de 0 et de 1, désignant si un objet sera retenu dans le sac à dos ou pas, par exemple:
    • x[3]=1 voudra dire que l'on choisit de retenir l'objet d'indice 3 pour le stocker dans le sac à dos.
    • x[3]=0 voudra dire le contraire: on ne retient pas cet objet pour être placé dans le sac à dos.

Principe de l'Algorithme Glouton itératif pour le Problème du Sac à Dos⚓︎

  1. ⚠Pré-Supposition⚠ (cf Exercice précédent) On suppose, avant même de commencer l'algorithme glouton itératif, que la sous-liste des objets=[nom,v,p,eff] correspondant à l'heuristique gloutonne choisie (v, p ou eff), soit déjà triée.
  2. Initialiser le poidsCourant à 0 (des objets actuellement placés dans le sac à dos). Initialiser la liste x des objets retenus à [0,0..,0]
  3. Pour chacun des objets, si l'ajout de l'objet suivant (dans l'ordre de l'heuristique gloutonne choisie) ne provoque pas un dépassement de poids, alors on retient cet objet en paramétrant convenablement la variable x pour cet objet, sinon on ne le retient pas
  4. A la fin du parcours de tous les objets, la varaible x contient les objets retenus

Remarque

Remarquons que cette méthode correspond bien à une Heuristique Gloutonne, car elle se résume à commencer par choisir systématiquement l'objet le plus gros selon l'heuristique choisie.

Pseudo-code de l'Algorithme Glouton Itératif

En pseudo-code, Proposer un algorithme glouton itératif pour le problème du Sac à Dos.

Implémentation Python⚓︎

Implémentation en Python

  1. Dans le langage de programmation Python, Proposer un algorithme glouton itératif contenant une fonction sacADosGlouton(objets=[nom,v,p]:list,heuristique:str)->x:list qui renvoie la liste des objets retenus.
  2. Comment calculer la valeur de la solution, i.e. le nombre d'objets retenus?
  3. Comment calculer la solution, i.e. le détails de quels objets ont été retenus?
  4. Étudier la Terminaison de cet algorithme glouton itératif pour le problème du Sac à Dos
  5. Étudier la Complexité de cet algorithme glouton itératif pour le problème du Sac à Dos

Une Application : des Vidéos sur une clé USB⚓︎

Nous disposons d’une clé USB qui est déjà bien remplie et sur laquelle il ne reste que 5 Go de libre. Nous souhaitons copier sur cette clé des fichiers vidéos pour l’emporter en voyage. Chaque fichier vidéo a un nom, une taille et une durée. La durée n’est pas proportionnelle à la taille car les fichiers sont de format différents, certaines vidéos sont de grande qualité, d’autres sont très compressées. Le tableau qui suit présente les fichiers disponibles avec les durées données en minutes.

Le Problème
Comme nous sommes en vacances... Le problème est de maximiser la durée des films emmenés, mais avec une Taille Maximale de \(5 \, Go\).

Fichier Durée Taille
Vidéo \(1\) \(114 \,\) \(4,57\) Go
Vidéo \(2\) \(32\) \(630\) Mo
Vidéo \(3\) \(20\) \(1,65\) Go
Vidéo \(4\) \(4\) \(85\) Mo
Vidéo \(5\) \(18\) \(2,15\) Go
Vidéo \(6\) \(80\) \(2,71\) Go
Vidéo \(7\) \(5\) \(320\) Mo

Représentation des données

Lister plusieurs manières de représenter les données en Python

Force Brute⚓︎

Limites de l'Algorithme Glouton⚓︎

Nous avons vu que l'algorithme Glouton ne donne, en général, pas une solution optimale. On pourrait penser qu'une bonne idée serait de parcourir toutes les solutions, on pourrait ainsi au moins déterminer la solution optimale (Force Brute). Il est un fait connu que c'est une très mauvaise idée du point de vue de la complexité (en temps). Voyons néanmoins comment on pourrait faire cela.

Force Brute⚓︎

Sur le papier, le principe est simple, il faut tester tous les cas possibles. La mise en oeuvre pratique l’est moins. Comment obtenir tous les cas sans les répéter et sans en oublier un ? Cette question pose la difficulté principale. Une méthode est d’associer le chiffre \(1\) à un fichier s’il est choisi et le chiffre \(0\) sinon. Nous obtenons ainsi un nombre entier écrit en binaire avec \(7\) chiffres.

Exp

  • Le nombre \(1001100\) signifie que nous avons choisi les fichiers \(1\), \(4\) et \(5\).
  • Le nombre \(1111111\) signifie que nous avons choisi tous les fichiers.
  • A chaque nombre correspond exactement une possibilité pour construire une partie de l’ensemble des \(7\) fichiers.
  • Il apparaît alors que le nombre total de cas est \(2^7\) puisqu’avec \(7\) chiffres nous pouvons écrire exactement \(2^7\) nombres.

Ex

  1. Écrire une fonction Python int_to_bin(n:int,nbits:int)->ch:str qui convertit un nombre entier n en binaire codé sur nbits bits. On pourra utiliser, ou pas, la fonction native de Python bin
  2. Écrire une fonction Python ens_des_parties(ensemble:list de tuples)->parties:list qui prend en paramètres un ensemble de notre problème des 7 fichiers, et renvoie l'ensemble des parties pouvant être consituées.
  3. Écrire une fonction Python duree_totale(liste:list)->d:int qui prend en paramètres la liste des vidéos, et qui renvoie la durée totale de la liste
  4. Écrire une fonction Python taille_totale(liste:list)->t:int qui prend en paramètres la liste des vidéos, et qui renvoie la taille totale de la liste
  5. Écrire une fonction Python recherche(ense_parties:list,contrainte:int)->solution:list, duree_max:int qui prend en paramètres un ensemble de parties et la contrainte, et renvoie la partie correspondant au meilleur choix satisfaisant la contrainte après avoir parcouru toutes les parties.
  6. Écrire une fonction Python force_brute(fichiers:list,taille_max:int)->recherche(parties,taille_max) qui prend en paramètres la liste des fichiers et la taille_max, et qui renvoie le résultat de recherche(parties, taille_max).
  7. Conclure