Introduction

Les problèmes d'optimisation sont particulièrement importants en informatique et ont bien des applications concrètes.

On peut penser par exemple la recherche du plus court chemin pour aller d’un point A à un point B, à l’optimisation de la mémoire en fonction des processus en cours d’exécution.

Dans de nombreux cas, on ne peut pas vérifier toutes les possibilités pour trouver ensuite la solution optimale à un problème car la complexité algorithmique peut être exponentielle, voire factorielle.

Alors, on a recours à d’autres techniques, dont l’utilisation d’algorithmes gloutons fait partie.

Après avoir expliqué ce qu’était un algorithme d’optimisation et un algorithme glouton, nous allons présenter deux problèmes d’optimisation pour lesquels nous utiliserons des algorithmes gloutons :

• Le problème de rendu de monnaie
• Le problème du sac à dos

1) Définitions

1.1) Problème d’optimisation

Le but d’un algorithme glouton est soit de trouver la solution optimale à un problème d’optimisation, soit de fournir une solution approximative.

Problème d'optimisation

Un problème d’optimisation consiste à trouver la meilleure solution selon certains critères dans un ensemble de solutions possibles. Au niveau mathématique cela consiste à maximiser ou minimiser une fonction.

1.2) Algorithme glouton

Un algorithme est dit glouton si les deux conditions suivantes sont vérifiées :

• A chaque étape, on effectue le meilleur choix possible localement
• On ne remet jamais en cause les choix précédents

Exemple

Supposons que je souhaite trouver la colline dont la hauteur est la plus élevée dans une certaine zone (disons dans un rayon de 5km). Alors, je vais choisir à chaque pas la direction pour laquelle la pente est la plus élevée.

En fonction de où je démarre ma recherche, je pourrais soit trouver le maximum global, soit ne trouver qu’un maximum local.

2) Exemple du problème de rendu de monnaie

Problème de rendu de monnaie

Vous avez à votre disposition un nombre illimité de pièces de 2 cts, 5 cts, 10 cts, 50 cts et 1 euro (100 cts). Vous devez rendre une certaine somme (rendu de monnaie).

Le problème est le suivant : "Quel est le nombre minimum de pièces qui doivent être utilisées pour rendre la monnaie"

Dans le cas d’un algorithme glouton, on cherche une solution locale étape par étape en essayant d’obtenir un optimum global.

Un algorithme glouton pour le problème de rendu de monnaie consiste à essayer à chaque fois avec la plus grande pièce telle que la valeur de cette pièce soit inférieur ou égale à la monnaie restant à rendre jusqu’à ce que la somme à rendre soit nulle.

• Appliquer cette méthode pour une somme de 1 € 57 (157cts) à rendre.
• Appliquer cette méthode à la somme de 21 centimes.
  • Quel est le problème ?
  • Proposer une solution permettant de rendre 21 centimes.

Ci-dessous, un exemple d’un cas où l’algorithme glouton trouve bien la solution optimale. Il faut rendre 36 centimes et le nombre minimum de pièces à utiliser est bien quatre.

3) Exemple du problème du sac à dos

Le problème du sac à dos à de nombreuses applications pratiques comme l'optimisation de la gestion des stocks, dans la découpe de matériaux, afin de minimiser les pertes dues aux chutes etc

Un cambrioleur de livres possède un sac à dos d'une contenance maximum de 10 kg. Au cours d'un de ses cambriolages, il a la possibilité de dérober 5 livres A, B, C, D et E. Voici un tableau qui résume les caractéristiques de ces objets :

Livre	A	B	C	D	E
masse en kg	5	4	5	4	10
valeur en $	10	9	5	10	4

Si on s’amusait à tester toutes les possibilités, alors on obtiendrait un algorithme à la complexité exponentielle. Quand le nombre d'objets devient élevé, l’algorithme devient inutilisable en pratique.

Quand le nombre d'objets devient élevé, l’algorithme devient inutilisable en pratique.

Une stratégie gloutonne

Une stratégie possible consiste à prendre toujours l'objet de plus grand rapport valeur / masse n'excédant pas la capacité restante.

On divise la valeur de chaque objet par sa masse :

Livre	A	B	C	D	E
valeur / masse	2	2.25	1	2.5	0.4

On commence par ajouter le livre D, c’est celui qui maximise le gain par rapport à la masse et qui est d’un poids inférieur ou égal au poids total que le sac peut contenir :

1ère étape : on prend le livre D Notre gain est de 10$ Il nous reste une capacité de 10 - 4 = 6 kg

2ème étape : on prend parmi les livres restants celui qui a le rapport valeur / masse maximal, c'est -à -dire le livre B. Notre gain est de 10$ + 9$ = 19$ Il nous reste une capacité de 6 kg - 4 kg = 2 kg

On ne peut plus faire rentrer de livre dans notre sac, on s’arrête là et notre gain est de 19$. Or, on voit rapidement que dans ce cas le gain n’est pas maximal, puisque prendre le livre D et ensuite le livre A aurait permis de maximiser le gain.

Conclusion

Nous avons vu que dans certains cas les algorithmes gloutons permettent de trouver des solutions optimales et dans d’autres cas, elles nous permettent uniquement de trouver une solution approchée.

Dans certains cas, on peut faire appel à une autre technique algorithmique : la programmation dynamique, que nous étudierons en Terminale, mais évidemment, n’hésitez pas à faire des recherches sur ce sujet !

En TP nous reviendrons à la fois sur le problème de rendu de monnaie et le problème du sac à dos.