Programmation dynamique et gloutonne¶

Deux stratégies pour résoudre des problèmes d'optimisation — l'une garantit l'optimalite au prix d'une exploration systematique, l'autre parie sur des choix locaux pour atteindre un optimum global.

Le problème de l'optimisation¶

Un problème d'optimisation cherche la meilleure solution parmi un ensemble (souvent exponentiel) de solutions candidates. La force brute — énumérer toutes les solutions — est correcte mais rarement acceptable. Les deux stratégies de ce chapitre exploitent la structure du problème pour éviter cette énumération.

Programmation dynamique : decomposer le problème en sous-problèmes qui se chevauchent, résoudre chaque sous-problème une seule fois et memoriser le résultat. Garantit l'optimum si deux conditions sont satisfaites.

Algorithme glouton : à chaque étape, faire le choix localement optimal en esperant que ces choix locaux menent à l'optimum global. Plus rapide, mais ne fonctionne que sur des problèmes a propriété spécifique.

Sous-structure optimale et chevauchement de sous-problèmes¶

La programmation dynamique repose sur deux propriétés structurelles.

Sous-structure optimale¶

Un problème a une sous-structure optimale si la solution optimale du problème contient les solutions optimales de ses sous-problèmes.

Exemple : le plus court chemin de A a C passant par B. Si ce chemin est optimal, alors le chemin de A a B est le plus court chemin de A a B, ET le chemin de B a C est le plus court chemin de B a C. Si l'un des deux troncons n'etait pas optimal, on pourrait le remplacer et obtenir un chemin encore plus court — contradiction.

Contre-exemple : le plus long chemin simple (sans répétition de sommet) n'a pas de sous-structure optimale. Le plus long chemin de A a C via B n'implique pas que le troncon A→B est le plus long chemin simple de A a B (ce troncon doit éviter les sommets que le troncon B→C a déjà utilisés). Cette dépendance contextuelle casse la sous-structure.

Chevauchement de sous-problèmes¶

Un problème a un chevauchement de sous-problèmes si la résolution recursive du problème résout les mêmes sous-problèmes plusieurs fois.

Fibonacci naif : fib(5) appelle fib(4) et fib(3). fib(4) appelle fib(3) et fib(2). fib(3) est calcule deux fois. La complexité est O(2ⁿ) car l'arbre de recursion est exponentiellement large. La programmation dynamique résout ce problème en calculant chaque sous-problème une seule fois.

Memoisation (top-down) : Fibonacci avec cache¶

La memoisation est l'approche naturelle : écrire la recursion, ajouter un cache. On descend du problème vers les sous-problèmes, on met en cache les résultats, on ne recalcule pas.

def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

# fib(40) : ~330 millions d'appels
# fib(50) : ~300 milliards d'appels (impraticable)

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

# fib(1000) : 1000 appels, O(n) temps, O(n) espace

def fib(n: int, memo: dict = None) -> int:
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

Analyse : chaque valeur de fib(k) est calculee exactement une fois. L'arbre de recursion avec cache devient lineaire : O(n) appels, O(n) espace pour le cache et la pile.

Avantage de la memoisation : on n'a pas besoin de déterminer l'ordre de calcul des sous-problèmes à l'avance. La recursion explore les dépendances naturellement et le cache evite les repetitions. Idéal pour des problèmes ou l'espace des sous-problèmes n'est pas complètement explore (certains sous-problèmes ne sont jamais atteints).

Tabulation (bottom-up) : même problème, tableau iteratif¶

La tabulation remplacé la recursion par une boucle iterative. On détermine l'ordre de calcul correct (des petits sous-problèmes vers les grands), on remplit un tableau.

def fib_tab(n: int) -> int:
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

def fib_opt(n: int) -> int:
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

Analyse : O(n) temps, O(1) espace (version optimisee). La tabulation permet souvent de réduire l'espace en n'conservant que les dernières valeurs nécessaires. Pour Fibonacci : seuls dp[i-1] et dp[i-2] sont nécessaires, donc O(1) suffit.

Avantage de la tabulation : pas de recursion donc pas de risque de stack overflow pour de grands n. Souvent plus rapide (pas de surchargé des appels de fonction). Permet l'optimisation de l'espace (ne conserver que les lignes nécessaires dans un tableau 2D).

Algorithmes gloutons : principe et preuve d'optimalite¶

Un algorithme glouton construit la solution en faisant à chaque étape le choix localement optimal, sans revenir en arriere. Sa simplicité et son efficacité (souvent O(n log n) ou O(n)) en font le choix préféré quand il est applicable.

Quand un glouton est-il optimal ? La propriété de choix glouton : un choix localement optimal peut toujours être incorpore dans une solution globalement optimale. Se prouve généralement par un argument d'échange.

Argument d'échange : supposer qu'une solution optimale OPT ne fait pas le choix glouton a une étape. Montrer qu'on peut modifier OPT pour qu'il fasse ce choix glouton sans dégrader la qualité de la solution. Donc le glouton produit au moins une solution aussi bonne que OPT.

Exemples détaillés¶

Fibonacci et sac a dos 0-1 (programmation dynamique)¶

Le sac a dos 0-1 : n objets, chaque objet i a un poids w[i] et une valeur v[i]. Capacité totale W. Maximiser la valeur totale sans dépasser W. Chaque objet est soit pris (1) soit laisse (0).

def sac_a_dos(poids: list, valeurs: list, W: int) -> int:
    n = len(poids)
    # dp[i][w] = valeur max avec les i premiers objets et capacite w
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(W + 1):
            # Ne pas prendre l'objet i
            dp[i][w] = dp[i - 1][w]
            # Prendre l'objet i si possible
            if poids[i - 1] <= w:
                dp[i][w] = max(dp[i][w],
                               dp[i - 1][w - poids[i - 1]] + valeurs[i - 1])

    return dp[n][W]

Complexité : O(n × W) temps et espace. C'est une complexité pseudo-polynomiale : polynomiale en n et W, mais exponentielle en la taille de la représentation binaire de W. Pour W = 10¹⁰, le tableau est impraticable. Le sac a dos 0-1 est NP-complet — cette solution DP est optimale en pratique pour W modere.

Optimisation espace : le tableau 2D peut être réduit a une seule ligne en parcourant w de droite à gauche (evite d'utiliser dp[i][w - p] qui serait déjà mis à jour pour l'iteration courante) :

def sac_a_dos_opt(poids, valeurs, W):
    dp = [0] * (W + 1)
    for p, v in zip(poids, valeurs):
        for w in range(W, p - 1, -1):  # Droite a gauche
            dp[w] = max(dp[w], dp[w - p] + v)
    return dp[W]

Plus longue sous-sequence commune (LCS)¶

Etant données deux sequences X et Y, trouver la plus longue sous-sequence (pas forcement contigue) commune aux deux. Exemple : LCS("ABCBDAB", "BDCAB") = "BCAB" de longueur 4.

def lcs(X: str, Y: str) -> int:
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

Complexité : O(m × n) temps et espace. Applications : diff de fichiers (Git utilise une variante), comparaison de sequences ADN (alignement de sequences), correction orthographique (distance d'edition de Levenshtein est une generalisation).

Codage de Huffman (algorithme glouton)¶

Huffman (1952) construit un code a longueur variable optimal pour la compression. Les caractères fréquents reçoivent des codes courts, les rares des codes longs.

Algorithme : placer tous les caractères dans une file de priorité (min-heap) selon leur fréquence. Répéter jusqu'à ne plus avoir qu'un élément : extraire les deux moins fréquents, créer un nœud parent dont la fréquence est leur somme, reinserrer.

import heapq

def huffman(freq: dict) -> dict:
    heap = [(f, c) for c, f in freq.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        f1, c1 = heapq.heappop(heap)
        f2, c2 = heapq.heappop(heap)
        # Noeud interne representant la fusion
        heapq.heappush(heap, (f1 + f2, (c1, c2)))

    def extraire_codes(noeud, prefixe="", codes={}):
        if isinstance(noeud, str):
            codes[noeud] = prefixe or "0"
        else:
            gauche, droite = noeud
            extraire_codes(gauche, prefixe + "0", codes)
            extraire_codes(droite, prefixe + "1", codes)
        return codes

    _, racine = heap[0]
    return extraire_codes(racine)

# Exemple
freq = {'a': 45, 'b': 13, 'c': 12, 'd': 16, 'e': 9, 'f': 5}
# Codes : a=0, c=100, b=101, f=1100, e=1101, d=111

Complexité : O(n log n) — n insertions/extractions du heap.

Preuve d'optimalite (argument d'échange) : les deux symboles de fréquence minimale sont toujours les plus profonds dans l'arbre optimal (sinon échanger avec des nœuds plus profonds reduirait la longueur totale). Donc placer les deux minimums comme feuilles sœurs est toujours correct.

Applications : DEFLATE (ZIP, gzip, PNG), JPEG (partie Huffman), MPEG, protocoles de compression de paquets réseau.

Rendu de monnaie : glouton vs dynamique¶

Le problème du rendu de monnaie illustre parfaitement la distinction entre les deux approches.

Problème : rendre un montant M avec un ensemble de pieces de valeurs données, en minimisant le nombre de pieces.

def rendu_glouton(pieces: list, montant: int) -> list:
    """Fonctionne uniquement pour des systemes de pieces canoniques."""
    pieces_triees = sorted(pieces, reverse=True)
    rendu = []
    for piece in pieces_triees:
        while montant >= piece:
            rendu.append(piece)
            montant -= piece
    return rendu if montant == 0 else []  # Echec si montant non atteignable

# Systeme euro [1, 2, 5, 10, 20, 50, 100, 200] : glouton optimal
# rendu_glouton([1, 2, 5, 10, 20, 50], 41) -> [20, 20, 1]

def rendu_dp(pieces: list, montant: int) -> int:
    """Nombre minimal de pieces, toujours optimal."""
    dp = [float('inf')] * (montant + 1)
    dp[0] = 0

    for m in range(1, montant + 1):
        for piece in pieces:
            if piece <= m and dp[m - piece] + 1 < dp[m]:
                dp[m] = dp[m - piece] + 1

    return dp[montant] if dp[montant] != float('inf') else -1

# pieces = [1, 3, 4], montant = 6
# Glouton : 4 + 1 + 1 = 3 pieces
# DP : 3 + 3 = 2 pieces (optimal)

Le glouton échoué sur pieces = [1, 3, 4], montant = 6 : il choisit 4 (plus grande piece ≤ 6), puis 1, puis 1 — total 3 pieces. La DP trouve 3 + 3 — 2 pieces. Le système de pieces euro et centimes est "canonique" (le glouton y est prouve optimal), mais ce n'est pas vrai pour tout système.

Complexité DP : O(n × M) ou n est le nombre de pieces et M le montant. O(M) espace.

Applications en systèmes réels¶

Optimisation de requêtes SQL¶

Un optimiseur de requêtes SQL (PostgreSQL, MySQL) doit choisir l'ordre des jointures et l'index a utiliser. Pour n tables, il existe n! ordres de jointure possibles. Les optimiseurs utilisent la programmation dynamique pour trouver le plan optimal en O(2ⁿ × n) au lieu de O(n!) : sous-structure optimale (le meilleur plan pour joindre {A, B, C} incorpore le meilleur plan pour joindre {A, B}), sous-problèmes qui se chevauchent (la jointure {A, B} est évaluée une fois, reutilisee pour {A, B, C} et {A, B, D}).

Pour n > 10-12 tables, même la DP devient coûteuse et les optimiseurs passent a des heuristiques gloutones (geedy join ordering).

Compression et Huffman dans les protocoles¶

Le format DEFLATE (RFC 1951), utilisé dans ZIP, gzip et PNG, combine LZ77 (élimination des sequences répétées) et Huffman (encodage des symboles restants). Huffman est appliqué séparément aux litteraux/longueurs et aux distances de référence. Cette combinaison explique pourquoi ZIP est efficace sur du texte (beaucoup de repetitions + distribution asymetrique des caractères) mais n'amélioré pas les fichiers JPEG (déjà compresses).

Allocation de cache avec programmation dynamique¶

Un système de cache distribué (Redis Cluster, CDN) doit décider quels objets stocker dans quel nœud avec quelle capacité. Si les objets ont des tailles différentes et des taux d'accès différents, c'est une instance du sac a dos fractionnable (continu) — résolu par un glouton (trier par ratio valeur/poids) — ou du sac a dos entier — résolu par DP si les capacités sont bornees.

Le cache LRU (Least Recently Used) est lui-même un glouton : evict toujours l'objet le moins récemment utilisé. Ce choix local ne maximise pas la précision future du cache (le remplacement optimal de Belady est omniscient), mais est simple, implementable en O(1) par access via une liste doublement chaînée + table de hachage, et donne de très bonnes performances empiriques.