Algorithmique 2 / Algorithmes de classification et d'optimisation

Problème du sac à dos

On dispose d'un sac à dos pouvant contenir au maximum $\rm 27~ kg$.

On dispose des objets suivants donné avec leur masse et leur valeur.

Approche gloutonne :

Pour essayer de résoudre ce problème, on peut utiliser une approche dite gloutonne.
On choisit les objets de plus grande valeur à condition que la contrainte sur la masse totale soit respectée.

Avec cette approche, on choisit successivement :

• L'objet de $\rm 14~ kg$ d'une valeur de $100 €$.
  
• L'objet de $\rm 8 ~kg$ d'une valeur de $90 €$.
  

On obtient ainsi une masse totale de $\rm 22~ kg$ pour une valeur totale de $190 €$.

Est-ce la meilleure solution ?

\[\begin{array}{|c|c|c|c|}
\hline
\rm Objet & \rm Masse & \rm Valeur & \text{Valeur massique}\\
\hline
\rm A & \rm 11~kg & 70€ & \rm \approx 6,36€/kg\\
\hline
\rm B & \rm 6~kg & 80€ & \rm \approx 13,33€/kg\\
\hline
\rm C & \rm 14~kg & 100€ & \rm \approx 7,14€/kg\\
\hline
\rm D & \rm 6~kg & 40€ & \rm \approx 6,67€/kg\\
\hline
\rm E & \rm 8~kg & 90€ & \rm \approx 11,25€/kg\\
\hline
\end{array}\]

En utilisant comme critère la valeur massique et en utilisant toujours une approche gloutonne, on choisit successivement :

• L'objet de $\rm 6~ kg$ d'une valeur de $80 €$ ;
  
• L'objet de $\rm 8~ kg$ d'une valeur de $90 €$ ;
  
• L'objet de $\rm 6 ~kg$ d'une valeur de $40 €$.
  

On obtient ainsi une masse totale de $\rm 20~ kg$ pour une valeur totale de $210 €$.

On a amélioré la valeur totale des objets (de $20 €$).

Existe-t-il une meilleure solution ?

On se rend facilement compte que oui.

Voici une solution dite optimale.

On choisit :

• L'objet de $\rm 11~kg$ d'une valeur de $70 €$
  
• L'objet de $\rm 6~kg$ d'une valeur de $80 €$
  
• L'objet de $\rm 8 kg$ d'une valeur de $90 €$

On obtient alors une masse totale de $\rm 25 kg$ pour une valeur totale de $240 €$.

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.

Voici cet arbre binaire représenter en partie (pour les 3 premiers niveaux : objets $\rm A$, $\rm B$ et $\rm C$).

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$.

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 $\rm 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 $\rm (NP)$.

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 dite P (pour polynomiale).

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.

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.

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.

Exemple : quel est le cercle le plus proche du carré ?

Il s'agit du du cercle vert avec le numéro 1.
On peut alors classer le carré dans le nuage des points verts.
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)
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.

La recherche de voisinage est utilisée dans de nombreux domaines.

On peut citer :

• La reconnaissance de formes,
  
• La prédiction de séries temporelles,
  
• L'apprentissage automatique en intelligence artificielle.