Les algorithmes gloutons

Des fois, quand un problème est trop complexe à résoudre, on a recours à des algorithmes approchés, c’est à dire des algorithmes fournissant une solution proche de la solution exacte (sacrifice de la correction), mais en un temps généralement beaucoup plus court. Les algorithmes gloutons entrent dans cette catégorie d’algorithmes.

Principe

L’idée d’un algorithme glouton est d’approximer la solution à un problème par une succession de solutions localement optimales. Pour illustrer cela, considérons le problème du voyageur de commerce, que nous avons vu être NP-Complet.

Plutôt que de chercher une solution exacte, nous pouvons regarder la solution suivante : toujours se diriger vers le sommet le plus proche, c’est-à-dire choisir l’arête de poids minimal. Il s’agit d’un algorithme glouton : en chaque point, on minimise la distance à parcourir en un pas de temps. On a donc une décision localement optimale.

Toutefois, pour bien se rendre compte que cette solution n’est pas exacte, considérons le graphe suivant, pour lequel on déroule tous les chemins possibles :

glouton

On voit qu’en partant du sommet a, on se dirigera tout d’abord vers d (car à distance minimale), puis vers c et enfin b. Le chemin est donc de longueur totale de 12 mouvements. Toutefois, l’optimal est de 7 par le chemin a-c-d-b.

Il est important lorsque l’on utilise un algorithme approché comme celui-ci d’étudier sa précision. Ce point fait l’objet d’un article à part entière disponible ici.

Bien sûr cet algorithme n’est qu’un exemple d’algorithme glouton pour répondre au problème du voyageur de commerce. Plutôt que de choisir systématiquement le voisin le plus proche, on peut utiliser d’autres heuristiques. En voici quelques exemples :

  • Choisir le chemin de longueur minimale explorant k sommets restant (k pouvant valoir 2, 3 et plus, k=1 revenant au glouton précédemment présenté),
  • Choisir de s’approcher en priorité d’une zone du labyrinthe contenant un grand nombre de fromages,
  • Lancer de façon aléatoire plusieurs poursuites possibles pour le trajet à suivre, et retenir la meilleure…

Un cas où l’algorithme glouton est optimal

Considérons le problème du rendu de pièces de monnaie : On désire rendre un certain montant en euros, et on dispose des pièces suivantes : 1c, 2c, 5c, 10c, 20c, 50c, 1€, 2€. L’objectif est d’utiliser le moins de pièces possible pour rendre la monnaie.

Ici, un algorithme glouton cherchera à minimiser le nombre de pièces en rendant toujours la pièce de valeur la plus haute possible. Ainsi, si on veut rendre 3.27€, l’algorithme rendra d’abord 2€ (reste 1.27€), puis 1€ (reste 27c), 20c (reste 7c), 5c (reste 2c), et enfin 2c.

En cherchant toutes les combinaisons possibles, on se rend compte que c’est la solution optimale. Pour montrer cela, il suffit de remarquer que chaque pièce a une valeur au moins égale à deux fois la pièce de valeur inférieure. Il sera donc toujours plus rentable de rendre en priorité la pièce de plus haute valeur car on rendra une pièce au lieu de plusieurs.

A présent, considérons les pièces suivantes : 1c, 2c, 5c, 10c, 20c, 40c, 50c, 1€ dans le cas où on souhaite rendre 80c : l’algorithme glouton rendra donc 50c (reste 30c), puis 20c (reste 10c) et 10c, soit trois pièces. Toutefois, on peut le faire en rendant deux pièces de 40c. Il faut donc faire attention aux valeurs des pièces disponibles.

Publié le

Laisser un commentaire