On dispose d'un sac à dos pouvant contenir au maximum $27~ \text{kg}$. Ce problème classique d'optimisation consiste à maximiser la valeur des objets transportés tout en respectant la contrainte de poids.
Données du problème
On dispose des objets suivants donnés avec leur masse et leur valeur.
Approche gloutonne
Pour essayer de résoudre ce problème, on peut utiliser une approche gloutonne. Cette méthode consiste à choisir les objets de plus grande valeur à condition que la contrainte sur la masse totale soit respectée.
Application de l'algorithme glouton
Avec cette approche, on choisit successivement :
L'objet de $14~ \text{kg}$ d'une valeur de 100 €
L'objet de $8~ \text{kg}$ d'une valeur de 90 €
Résultat obtenu
On obtient ainsi une masse totale de $22~ \text{kg}$ pour une valeur totale de $190~ €$.
Question importante : Est-ce la meilleure solution ?
On obtient alors une masse totale de $\rm 25 kg$ pour une valeur totale de $240 €$.
Algorithme de recherche de la solution optimale
Quel est l'algorithme qui permet de trouver la solution optimale
C'est un algorithme qui teste toutes les possibilités de choix des différents objets. On décide pour chaque objet si on le prend ou non. On peut représenter toutes les possibilités à partir d'un arbre binaire.
Représentation par arbre binaire
Voici cet arbre binaire représenter en partie (pour les 3 premiers niveaux : objets $\rm A$, $\rm B$ et $\rm C$).
Complexité algorithmique
Une fois cet arbre construit, on cherche une branche de l'arbre qui respecte la contrainte du poids et qui maximise la valeur des objets. Dans notre exemple, nous avons 5 objets. Le nombre de chemins possibles dans l'arbre binaire est égal à $2^5 = 32$.
Problème de complexité exponentielle
Imaginons, un exemple avec $100$ ou $1~000$ objets, alors le nombre de cas à analyser serait respectivement de $2^{100}$ ou $2^{1000}$. Ces nombres sont gigantesques et même un ordinateur très puissant ne serait pas capable d'analyser tous les cas en une durée raisonnable. Ce type de problème est qualifié de problème NP, $\rm NP$ signifiant Non Polynomial.
En effet, la complexité algorithmique du problème du sac à dos croit de manière exponentielle par rapport au nombre d'objets. C'est pour cela que l'on peut classer la recherche optimale du problème du sac à dos comme un problème non polynomial (NP).
Algorithme glouton et classe P
Par contre, la durée d'exécution de l'algorithme glouton (qui ne donne pas toujours la solution optimale) croit linéairement avec le nombre d'objets. On peut classer donc cet algorithme glouton dans la classe P (pour polynomiale).
Autres exemples d'application de l'algorithme glouton
On peut citer d'autres exemples pour lesquels on peut appliquer un algorithme glouton :
Le problème du rendu de monnaie
On doit rendre une somme donnée en utilisant un minimum de pièces/billets.
Des problèmes de coloration de graphes
Décomposition d'une fraction en somme de fractions égyptiennes
Une fraction égyptienne a toujours un numérateur égal à $1$.
Le problème du sac à dos fait partie des 21 problèmes NP-complets identifiés par Richard Karp en 1972. Ces 21 problèmes sont réputés comme les problèmes les plus difficiles en optimisation combinatoire. Un grand nombre d'autres problèmes NP-complets peuvent se ramener à ces 21 problèmes de base.
Applications du problème du sac à dos
Nous pouvons retrouver le problème du sac à dos dans de nombreux domaines :
En cryptographie, où il fut à l'origine du premier algorithme de chiffrement asymétrique en 1976 ;
Dans les systèmes financiers, où l'idée est la suivante : étant donné un certain montant d'investissement dans des projets, quels projets choisir pour que le tout rapporte le plus d'argent possible ? ;
Pour la découpe de matériaux, afin de minimiser les pertes dues aux chutes ;
Dans le chargement de cargaisons (avions, camions, bateaux…).
On dispose d'un nuage de points définis sur deux dimensions.
Dans cet exemple, nous avons 20 points de couleur rouge et 20 points de couleur verte représentés par des cercles.
Méthode de classification
On place un carré sur le quadrillage et on souhaite apprécier si le carré est "plus proche" du nuage de points de couleur rouge ou bien de celui de couleur verte. Pour cela, on peut utiliser la distance euclidienne entre le carré et les différents cercles des deux nuages de points.
Classification avec le plus proche voisin (k=1)
Exemple
Quel est le cercle le plus proche du carré ?
Il s'agit du cercle vert avec le numéro 1. On peut alors classer le carré dans le nuage des points verts.
Classification avec les 3 plus proches voisins (k=3)
On peut aussi déterminer quels sont les 3 cercles les plus proches du carré.
Nous trouvons alors 2 cercles rouges numérotés 2 et 3 pour un cercle vert numéroté 1. Avec le critère des 3 plus proches voisins, on peut classer le carré avec le nuage des cercles rouges (2 rouges > 1 vert).
Classification avec les 5 plus proches voisins (k=5)
De même avec un critère des 5 plus proches voisins, on obtient :
Soit 3 cercles rouges pour 2 cercles verts : le carré est encore à rapprocher du nuage de points rouge.
Retour
