Qu'est-ce que les algorithmes gloutons et quand fonctionnent-ils ?

Question

Accepted Answer

Un **algorithme glouton** fait le **choix localement optimal** à chaque étape, en espérant qu'il mène à un optimum global. Il est simple et rapide, mais ne fonctionne correctement que si le problème possède la **propriété de choix glouton** et la **sous-structure optimale**.

## L'idée

Ne jamais reconsidérer les choix passés — s'engager dans la meilleure option immédiate et continuer.

## Exemple : rendu de monnaie avec pièces canoniques

```python
def greedy_coins(amount, coins=(25, 10, 5, 1)):
    result = []
    for coin in coins:                 # largest first
        while amount >= coin:
            amount -= coin             # take as many as possible
            result.append(coin)
    return result

greedy_coins(36)                       # -> [25, 10, 1]
```

Ceci est optimal pour les pièces américaines, mais **échoue** pour des ensembles comme {1, 3, 4} où le glouton donne 4+1+1 pour 6 au lieu de 3+3.

## Quand le glouton fonctionne

- **Sous-structure optimale :** une solution optimale contient des sous-solutions optimales.
- **Propriété de choix glouton :** un optimum local fait partie d'un optimum global.

Exemples qui fonctionnent : Dijkstra, Kruskal/Prim (MST), codage Huffman, ordonnancement d'intervalles.

## Complexité

Généralement rapide — souvent O(n log n) après tri.

## Pièges

Le glouton n'est **pas toujours correct**. Prouvez la propriété de choix glouton ou testez par rapport à une baseline de force brute/DP avant de lui faire confiance.

## Pourquoi c'est important

Quand le glouton s'applique, il est bien plus simple et rapide que la DP ou la force brute.

Savoir *quand* il est valide — et quand il donne silencieusement des mauvaises réponses — est une marque de maturité algorithmique.

Beaucoup d'algorithmes graphiques fondamentaux sont gloutons par essence.