Algorithmes gloutons

Algorithmes gloutons

Principe

Un algorithme glouton construit une solution étape par étape, en faisant à chaque étape le choix localement optimal, sans jamais revenir en arrière. Il est rapide mais ne garantit pas toujours la solution optimale globale.

Un algorithme glouton est correct quand le problème vérifie la propriété du choix glouton (un choix optimal local conduit à une solution globale optimale) et la sous-structure optimale.

Rendu de monnaie

Rendre $S$ avec le moins de pièces possible parmi $\{1, 2, 5, 10, 20, 50\}$. La stratégie gloutonne (prendre à chaque étape la plus grosse pièce $\le S$) est optimale pour le système monétaire européen, mais pas pour tous : avec $\{1, 3, 4\}$ et $S = 6$, le glouton donne $4+1+1 = 3$ pièces, alors que l'optimum est $3+3 = 2$ pièces.

def rendu(s, pieces=[50, 20, 10, 5, 2, 1]):
    res = []
    for p in pieces:
        while s >= p:
            res.append(p); s -= p
    return res

Sac à dos fractionnaire

On dispose d'objets $(v_i, p_i)$ et d'un sac de capacité $W$. On peut prendre des fractions d'objets. Stratégie gloutonne optimale : trier les objets par valeur par unité de poids $v_i / p_i$ décroissante, prendre chaque objet entièrement tant que possible, puis une fraction du suivant.

(Pour le sac à dos 0/1, le glouton n'est pas optimal ; il faut la programmation dynamique.)

Ordonnancement de tâches

Sélection d'activités non chevauchantes : trier par heure de fin croissante, prendre la première compatible puis itérer. Optimal.

def planning(taches):  # taches = [(debut, fin), ...]
    taches.sort(key=lambda t: t[1])
    res, fin_prec = [], -float('inf')
    for d, f in taches:
        if d >= fin_prec:
            res.append((d, f)); fin_prec = f
    return res

Complexité

Souvent dominée par un tri initial : $O(n \log n)$.