Algorithmes gloutons

Bonjour ! C’est encore moi. Je vois que vous avez faim d’en savoir plus sur la théorie des graphes. Moi aussi !

Parfois, lorsqu’un problème est trop complexe à résoudre, on utilise des algorithmes d’approximation. Les algorithmes d’approximation fournissent une solution proche de la solution exacte, mais dans un temps beaucoup plus court. Un exemple d’algorithmes d’approximation sont les algorithmes gloutons.

Le but d’un algorithme glouton est d’approximer la solution d’un problème par une succession de solutions localement optimales. Pour illustrer cela, considérons le problème du voyageur de commerce, le TSP, dont nous avons vu qu’il est un problème complexe à résoudre.

Au lieu de chercher une solution exacte, nous pouvons choisir d’aller toujours vers le sommet non exploré le plus proche du sommet où nous nous trouvons actuellement. Il s’agit d’un algorithme glouton car, à chaque étape, la distance à parcourir est minimisée, un pas à la fois. Nous avons donc pris des décisions localement optimales.

Cependant, cette solution n’est pas nécessairement optimale. Prenons le graphe suivant comme exemple, pour lequel nous explorons tous les chemins possibles.

Mettons l’algorithme glouton en pratique. En partant du sommet $v_1$, nous irons d’abord vers $v_4$, car l’arête correspondante est la plus courte de toutes les possibilités. En utilisant le même principe, nous nous déplacerons ensuite vers $v_3$ et enfin vers $v_2$. N’est-ce pas ? Dans cet exemple, le chemin obtenu a une longueur totale de 12.

Cependant, la solution optimale est un chemin qui a une longueur de 7, qui est le chemin $( {v_1,v_3}, {v_3,v_4}, {v_2,v_4} )$.

N’oubliez pas, cet algorithme n’est qu’un exemple d’algorithme glouton pour résoudre le TSP. En plus de choisir systématiquement le voisin le plus proche, qui était l’exemple que nous venons de voir, d’autres heuristiques peuvent être utilisées. Voici quelques exemples :

Vous pouvez choisir le chemin de longueur minimale en explorant $k$ sommets restants ($k = 2, 3, \dots$) ? Si $k = 1$, alors il s’agit de l’algorithme glouton simple que nous venons de voir, Vous pouvez choisir d’aller vers une zone dense d’un labyrinthe où il y a beaucoup de morceaux de fromage à trouver, Ou, vous pouvez choisir de lancer aléatoirement plusieurs recherches possibles, et retenir la meilleure option.

Dans certains cas, les algorithmes gloutons peuvent être optimaux.

Considérons le problème du rendu de monnaie après un paiement. Nous souhaitons rendre une certaine somme de monnaie en euros, et nous avons les pièces suivantes : 1c, 2c, 5c, 10c, 20c, 50c, 1€, 2€. L’objectif est d’utiliser le moins de pièces possible.

Un algorithme glouton typique consiste à sélectionner la pièce de valeur la plus élevée possible, inférieure à la somme qui doit être rendue, jusqu’au point où la monnaie restante à rendre est 0. Donc, si vous voulez rendre 3,27€, alors l’algorithme rendra d’abord 2€ (laissant 1,27€ à rendre), puis 1€ (laissant 27c à rendre), 20c (laissant 7c à rendre), 5c (laissant 2c à rendre), et enfin 2c.

En cherchant toutes les combinaisons possibles, on peut voir que c’est bien la solution optimale. Pour montrer cela, il suffit de remarquer que chaque pièce a une valeur au moins égale au double de la pièce de valeur inférieure. Cela signifie qu’il sera toujours plus efficace de donner la priorité à la pièce de valeur supérieure, car une pièce sera rendue au lieu de plusieurs.

Considérons maintenant les pièces suivantes : 1c, 2c, 5c, 10c, 20c, 40c, 50c, 1€, et dans ce cas nous voulons rendre 80c. L’algorithme glouton rendra 50c (reste 30c), puis 20c (reste 10c) et 10c, soit trois pièces.

Cependant, rendre 80c peut également se faire en rendant deux pièces de 40c. Dans ce cas, un algorithme glouton n’est pas optimal.

Pour récapituler, cette leçon vous a présenté les algorithmes gloutons pour trouver des solutions approximatives à des problèmes complexes tels que le TSP. À la prochaine !