Programmation dynamique

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

énoncer les deux conditions qui rendent la programmation dynamique applicable — sous-structure optimale et chevauchement des sous-problèmes — et vérifier chacune sur un problème donné au lieu de la supposer;
nommer le sous-problème et écrire sa récurrence avant d'écrire une ligne de code, en disant ce que l'indice parcourt et ce que la valeur signifie;
passer d'une récursion mémoïsée (descendante) à une table remplie dans l'ordre (ascendante), et justifier que les deux calculent exactement les mêmes valeurs;
remplir la table du sac à dos 0/1 sur une instance donnée, reconstruire la sélection optimale à partir de la table, et expliquer pourquoi le choix glouton du chapitre 9 échoue ici;
écrire la récurrence de la plus longue sous-séquence commune et de la distance d'édition, et lire la solution dans la grille;
réduire la mémoire à deux lignes, dire ce que cette réduction fait perdre, et reconnaître qu'un coût en $O (nW)$ n'est pas polynomial en la taille de l'entrée.

Deux conditions, et une discipline

Une méthode, pas un algorithme

La programmation dynamique n'est pas un algorithme: c'est un patron de conception, au même titre que diviser pour régner au chapitre 2 ou le choix glouton au chapitre 9. On ne l'apprend pas en mémorisant une procédure, on l'apprend en reconnaissant une situation. Cette situation est toujours la même: un problème d'optimisation dont les solutions optimales se composent à partir des solutions optimales d'un petit nombre de sous-problèmes, et dont une résolution récursive naïve recalcule sans cesse les mêmes.

Le nom mérite une remarque, parce qu'il est trompeur. Richard Bellman, qui a fixé la méthode dans les années 1950, a raconté avoir choisi «programmation dynamique» parce que le mot programming signifiait alors «planification» — la programmation linéaire est de la même famille — et parce qu'un intitulé au son technique protégeait ses crédits de recherche. Il n'est donc question ni de programmation au sens où vous l'entendez, ni de dynamique au sens de la physique. Retenez plutôt le nom que la méthode mériterait: calculer chaque sous-problème une fois et se souvenir du résultat.

Première condition: la sous-structure optimale

La formulation est abstraite; sa vérification ne l'est pas, et elle suit presque toujours le même schéma, dit argument de découpe-recollage (cut and paste): on suppose qu'une partie d'une solution optimale n'est pas optimale pour sa sous-instance, on la remplace par une meilleure, et l'on vérifie que le recollage donne une solution admissible de valeur strictement supérieure — ce qui contredit l'optimalité supposée. Nous mènerons cet argument en entier pour le sac à dos, au théorème 10.2. La partie qui demande de l'attention n'est jamais l'échange lui-même: c'est la vérification que le recollage reste admissible. Lorsqu'elle échoue, la méthode échoue, et la dernière section de ce chapitre montre un problème où elle échoue précisément.

Seconde condition: le chevauchement des sous-problèmes

C'est cette seconde condition qui sépare la programmation dynamique de diviser pour régner. Le tri fusion du chapitre 2 découpe lui aussi un problème en sous-problèmes, mais ses deux moitiés sont disjointes: aucun sous-tableau n'est trié deux fois, et il n'y a donc rien à mémoriser. La programmation dynamique s'applique quand les sous-problèmes se recoupent, c'est-à-dire quand l'arbre des appels récursifs est beaucoup plus gros que l'ensemble des sous-problèmes qu'il visite. Le rapport entre ces deux nombres est exactement le facteur que l'on gagne.

La discipline: nommer le sous-problème avant d'écrire une ligne

L'erreur de débutant, en programmation dynamique, n'est pas une erreur de code: c'est de se mettre à écrire des boucles imbriquées sur une table dont on ne sait pas dire ce que contient la case. Le remède est une discipline en quatre temps, que ce chapitre appliquera à chacun de ses problèmes et dont vous ne devez jamais sauter la première étape.

Nommer le sous-problème et dire ce que vaut la case. Une phrase complète, en français, avec ses quantificateurs: « $K (i, w)$ est la valeur maximale que l'on peut emporter en n'utilisant que les $i$ premiers objets, sans dépasser le poids $w$ ». Si vous ne savez pas écrire cette phrase, vous ne savez pas encore quel est votre sous-problème, et aucune boucle ne vous le dira.
Écrire la récurrence, en énumérant les choix possibles pour la dernière décision, et en disant sur quel sous-problème chacun renvoie.
Écrire les cas de base, c'est-à-dire les cases que la récurrence ne définit pas.
Fixer l'ordre de calcul: quel ordre garantit que les cases dont une case dépend sont déjà calculées quand on l'atteint? La mémoïsation répond à cette question toute seule; la tabulation exige que vous y répondiez.

La réponse à la question 1 doit être une phrase que vous pourriez lire à voix haute à quelqu'un qui ne connaît pas le problème. Elle contient en germe tout le reste: on trouve la récurrence en demandant «quelle est la dernière décision, et à quel sous-problème me ramène chaque valeur possible de cette décision?».

Question 10.1

Un algorithme diviser pour régner (tri fusion, recherche dichotomique) ne gagne rien à être mémoïsé. Pourquoi?

Le plus petit exemple possible: Fibonacci

Ce que coûte une belle définition

Vous avez rencontré cet exemple au chapitre 9 d'Introduction à la programmation, et nous ne le reprenons pas pour le réapprendre: nous le reprenons parce que c'est le plus petit objet sur lequel les deux conditions se voient à l'œil nu, et parce qu'il sert de mesure. Rappelons-le en trois lignes:

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

Notons $a_{n}$ le nombre d'appels engendrés par fib(n). On a $a_{0} = a_{1} = 1$ et $a_{n} = 1 + a_{n - 1} + a_{n - 2}$ , d'où, par récurrence immédiate, où est le -ième terme de la suite. Le nombre d'appels croît donc comme la suite elle-même, c'est-à-dire en avec .

La mesure qui compte tient en deux nombres. Pour $n = 25$ , l'appel fib(25) déclenche 242 785 appels — c'est $2 F_{26} - 1 = 2 \times 121393 - 1$ — alors qu'il n'existe que 26 valeurs distinctes à calculer, de $F_{0}$ à . La version mémoïsée du chapitre 9 d' en fait , c'est-à-dire . Le rapport est d'environ 4955, et il n'est pas constant: il croît exponentiellement avec , puisque l'une des deux versions est exponentielle et l'autre linéaire.

Les deux conditions sont lisibles sur la figure 10.1. La sous-structure optimale — ici, plus simplement, la sous-structure tout court, puisqu'il n'y a rien à optimiser — est la définition même: $F_{n}$ se calcule à partir de $F_{n - 1}$ et $F_{n - 2}$ , un point c'est tout. Le chevauchement est ce que le panneau du haut montre: fib(3) est calculé en entier deux fois, fib(2) trois fois, fib(1) cinq fois.

Descendante: la mémoïsation

def fib_memo(n, connus=None):
    """Version descendante: la recursion reste, la table evite les recalculs."""
    if connus is None:
        connus = {}
    if n in connus:
        return connus[n]
    valeur = n if n <= 1 else fib_memo(n - 1, connus) + fib_memo(n - 2, connus)
    connus[n] = valeur
    return

Le nombre d'appels tombe à $2 n - 1$ : un appel «calculant» par valeur distincte, soit $n + 1$ , et une lecture par arête qui pointe vers une valeur déjà connue, soit $n - 2$ . La ligne if n in connus n'est pas une optimisation accessoire: c'est la moitié du mécanisme. Remplir la table sans jamais la relire laisserait le coût exponentiel intact, comme le rappelle le quiz du chapitre 9 d'Introduction à la programmation.

Ascendante: la tabulation

def fib_table(n):
    """Version ascendante: aucune recursion, une seule boucle."""
    f = [0] * (max(n, 1) + 1)
    f[1] = 1
    for i in range(2, n + 1):
        f[i] = f[i - 1] + f[i - 2]
    return

Le coût saute aux yeux: $n - 1$ additions, aucun appel de fonction, aucune pile. Pour $n = 25$ , 24 additions contre 242 785 appels. La table f contient les mêmes 26 valeurs que le dictionnaire connus de la version descendante — mais elle les contient toutes, y compris celles dont le problème complet n'aurait pas eu besoin, alors que la version descendante ne remplit que ce que la récursion visite. Sur Fibonacci, la récursion visite tout, et la différence est nulle; nous verrons qu'elle ne l'est pas toujours.

Les deux versions calculent la même chose. Ce n'est pas une évidence — c'est un énoncé, et il se démontre.

Démonstration. La relation de dépendance étant acyclique sur un ensemble fini, elle est bien fondée: on peut raisonner par récurrence sur la hauteur $h (s)$ , définie par $h (s) = 0$ si $dep (s) = \emptyset$ et $h (s) = 1 + max_{t \in dep (s)} h (t)$ sinon. Cette hauteur est finie parce que est fini et la relation acyclique.

Point 1. Montrons par récurrence sur $h (s)$ que l'appel mémoïsé sur $s$ termine et renvoie $V (s)$ , quel que soit le contenu de la table pourvu qu'il soit correct, c'est-à-dire que toute case déjà remplie contienne la valeur $V$ du sous-problème correspondant.

Si la table contient déjà $s$ , l'appel renvoie ce contenu, qui vaut $V (s)$ par hypothèse de correction, et termine sans rien calculer. Sinon, si $h (s) = 0$ , l'appel renvoie la constante $Φ_{s} = V (s)$ et range cette valeur: la table reste correcte. Si $h (s) > 0$ , l'appel lance un appel sur chaque ; chacun vérifie , donc par hypothèse de récurrence chacun termine et renvoie , en laissant la table correcte — c'est ici que la récurrence doit porter sur «pour toute table correcte», sans quoi l'hypothèse ne s'appliquerait pas aux appels suivants, qui voient une table modifiée par les précédents. L'appel calcule alors , le range et le renvoie. La table reste correcte, et la terminaison suit de la finitude de .

Chaque sous-problème est calculé au plus une fois: dès qu'un appel calcule la valeur de $s$ , il la range immédiatement, et tout appel ultérieur sur $s$ trouve la case remplie et retourne sans descendre. Le nombre d'appels «calculants» est donc au plus $∣ S ∣$ , et le nombre total d'appels au plus $∣ S ∣ \cdot (1 + max_{s} ∣ dep (s)∣)$ .

Point 2. Soit $s_{1}, s_{2}, \dots, s_{N}$ un ordre topologique de $S$ , c'est-à-dire un ordre tel que toute dépendance de $s_{k}$ apparaisse avant ; un tel ordre existe pour tout graphe acyclique fini (chapitre 6). Montrons par récurrence sur que la case reçoit . Au moment où l'algorithme traite , toutes les cases contiennent déjà la bonne valeur par hypothèse de récurrence; or est inclus dans par définition de l'ordre topologique, donc l'algorithme lit exactement les valeurs pour et range de ces valeurs, c'est-à-dire .

Point 3. Les deux algorithmes rangent, dans toute case qu'ils remplissent, la valeur $V$ du sous-problème correspondant, qui est définie sans référence à aucun algorithme. Ils coïncident donc partout où ils sont tous deux définis. La seule différence porte sur l'ensemble des cases remplies: la tabulation les remplit toutes, la mémoïsation seulement celles que la récursion atteint depuis $s$ , c'est-à-dire les descendants de $s$ dans la relation de dépendance. $□$

Trois conséquences pratiques de cette démonstration méritent d'être retenues, parce qu'elles décident du choix entre les deux méthodes.

L'hypothèse d'acyclicité n'est pas décorative. Si un sous-problème dépend de lui-même, directement ou par un cycle, la valeur $V$ n'est pas définie et la mémoïsation boucle sans fin — ou pire, renvoie une valeur fausse si l'on a pris la précaution de marquer les cases «en cours». Les problèmes de plus courts chemins avec des arêtes qui reviennent en arrière sont exactement dans ce cas, et c'est pourquoi le chapitre 7 les traite par relaxation répétée plutôt que par mémoïsation.
La mémoïsation ne remplit que le nécessaire. Quand une grande partie de la table est inatteignable — capacités jamais rencontrées, indices jamais atteints —, la version descendante fait moins de travail que la version ascendante, parfois beaucoup moins.
La tabulation n'a pas de pile. La version descendante empile un cadre par niveau de récursion, et le chapitre 9 d'Introduction à la programmation rappelle que CPython s'arrête vers mille cadres imbriqués. La version ascendante n'a pas ce plafond, et ses accès contigus sont favorables au cache (chapitre 1).

Question 10.2

Remettez dans l'ordre les étapes de conception d'une solution par programmation dynamique.

Glissez les éléments pour les mettre dans le bon ordre

Écrire les cas de base, c'est-à-dire les cases que la récurrence ne définit pas

Écrire la récurrence en énumérant les choix possibles pour la dernière décision

Remplir la table, puis reconstruire la solution en remontant les choix

Dire en une phrase ce que vaut la case: «

K (i, w)

est la valeur maximale telle que …»

Fixer un ordre de calcul où toute case est remplie après celles dont elle dépend

Le sac à dos 0/1

Le problème et l'instance du cours

L'instance qui sert de témoin dans tout ce cours est la suivante, et elle est fixée: capacité $W = 9$ et quatre objets

Objet	$A$	$B$	$C$	$D$
Poids $p_{i}$	2	3	4	5
Valeur $v_{i}$	3	4	5	8
Rapport $v_{i} / p_{i}$

La solution par énumération exhaustive est immédiate — il n'y a que $2^{4} = 16$ sous-ensembles — et nous la calculerons pour disposer d'une vérité de référence: l'optimum vaut 13, atteint par ${C, D}$ , de poids $4 + 5 = 9$ , c'est-à-dire exactement la capacité. Cet optimum est unique: aucun autre sous-ensemble admissible n'atteint 13.

Mais $2^{n}$ sous-ensembles, c'est 16 pour quatre objets et plus d'un milliard pour trente. Le tableau des ordres de grandeur du chapitre 1 est sans appel: un algorithme exponentiel est hors de portée dès la trentaine d'objets, quelle que soit la machine. Il nous faut mieux.

Étape 1: nommer le sous-problème

Appliquons la discipline. Quelle est la dernière décision? Prendre ou ne pas prendre le dernier objet. Cette décision suggère d'indexer les sous-problèmes par le nombre d'objets que l'on s'autorise; et comme prendre un objet consomme de la capacité, il faut aussi indexer par la capacité restante. D'où la phrase, qu'il faut savoir énoncer avant tout:

$K (i, w)$ est la valeur maximale que l'on peut emporter en n'utilisant que les objets d'indices $0$ à $i - 1$ — les $i$ premiers objets — et sans dépasser le poids total $w$ .

Deux précisions que cette phrase contient et qu'il ne faut pas perdre. D'abord $i$ compte des objets, il n'en désigne pas un: $K (0, w) = 0$ parce qu'avec zéro objet on n'emporte rien. Ensuite $w$ est un majorant du poids, pas le poids exact: $K (i, w)$ est la meilleure valeur pour un poids au plus $w$ , ce qui rend la fonction croissante en $w$ et évite d'avoir à traiter séparément les cases où l'on n'utilise pas toute la capacité.

Étape 2: la récurrence

Considérons une solution optimale du sous-problème $(i, w)$ , avec $i \geq 1$ . Deux cas, et deux seulement, selon que l'objet $i - 1$ y figure ou non.

Il n'y figure pas. Alors cette solution n'utilise que les $i - 1$ premiers objets sous la contrainte $w$ , et c'est nécessairement la meilleure de ces solutions-là: sa valeur est $K (i - 1, w)$ .
Il y figure. Alors son poids est au moins $p_{i - 1}$ — ce cas n'est possible que si $p_{i - 1} \leq w$ — et le reste de la solution n'utilise que les premiers objets sous la contrainte . Sa valeur est donc .

La valeur optimale étant le meilleur des cas possibles:

K (i, w) = ⎩ ⎨ ⎧ 0 K (i - 1, w) max (K (i - 1, w), v_{i - 1} + K (i - 1, w - p_{i - 1})) si i = 0, si p_{i - 1} > w, sinon. (10.1)

Le raisonnement ci-dessus contient un pas que nous avons franchi trop vite, et c'est exactement le pas qu'il faut démontrer: pourquoi «le reste de la solution» est-il une solution optimale du sous-problème $(i - 1, w - p_{i - 1})$ ? Rien ne l'impose a priori.

Démonstration. Les deux points se démontrent par découpe-recollage, et il faut à chaque fois vérifier trois choses: que l'objet exhibé est admissible pour le sous-problème visé, qu'un concurrent strictement meilleur donnerait une solution admissible du problème initial, et que sa valeur y serait strictement plus grande.

Point 1. Supposons $i - 1 \in / S$ . Alors $S$ n'utilise que les $i - 1$ premiers objets et vérifie $\sum_{j \in S} p_{j} \leq w$ : c'est bien une solution admissible du sous-problème . Supposons par l'absurde qu'elle n'y soit pas optimale: il existe n'utilisant que les premiers objets, de poids au plus , et de valeur strictement supérieure à celle de . Mais est aussi une solution admissible du sous-problème — s'autoriser un objet de plus n'interdit pas de ne pas le prendre —, et sa valeur dépasse strictement celle de , ce qui contredit l'optimalité de pour .

Point 2. Supposons $i - 1 \in S$ et posons $S_{0} = S ∖ {i - 1}$ . Le poids de $S_{0}$ vaut , et n'utilise que les premiers objets: est donc admissible pour le sous-problème . Supposons par l'absurde qu'elle n'y soit pas optimale: il existe n'utilisant que les premiers objets, de poids au plus , et de valeur strictement supérieure à celle de . Recollons: posons . Cette réunion est disjointe puisque ne contient pas l'objet , donc

j \in S^{'} \sum p_{j} = j \in S_{0}^{'} \sum p_{j} + p_{i - 1} \leq (w - p_{i - 1}) + p_{i - 1} = w,

et $S^{'}$ est admissible pour le sous-problème $(i, w)$ . Sa valeur vaut $v (S_{0}^{'}) + v_{i - 1} > v (S_{0}) + v_{i - 1} = v (S)$ , ce qui contredit l'optimalité de .

La récurrence. Les deux points montrent que la valeur d'une solution optimale de $(i, w)$ est soit $K (i - 1, w)$ , soit $v_{i - 1} + K (i - 1, w - p_{i - 1})$ lorsque ; elle est donc au plus le maximum des deux. Réciproquement, chacune des deux quantités est atteinte par une solution admissible de — une solution optimale de dans le premier cas, une solution optimale de augmentée de l'objet dans le second, admissible par le calcul de poids ci-dessus —, donc est au moins le maximum des deux. D'où l'égalité (10.1). Le cas s'obtient de même en supprimant le second terme, impossible faute de place, et le cas est immédiat.

Ce que le recollage exige, et pourquoi il faut le vérifier

Regardez ce que la démonstration a réellement utilisé au point 2: que retirer l'objet $i - 1$ libère exactement $p_{i - 1}$ unités de capacité, et que le sous-problème obtenu ne contraint plus rien d'autre. C'est ce qui rend le recollage admissible, et c'est la seule chose qui le rende admissible.

Un problème où le sous-problème hériterait d'une contrainte supplémentaire — «ne pas réutiliser les objets déjà pris ailleurs», «ne pas repasser par un sommet déjà visité» — ne permettrait pas ce recollage: la meilleure solution du sous-problème pourrait être incompatible avec le reste. C'est exactement ce qui arrive au plus long chemin simple, à la fin de ce chapitre. La sous-structure optimale est une hypothèse à vérifier, pas une formalité.

Étape 3 et 4: les cas de base et l'ordre de calcul

Les cas de base sont donnés par la ligne $i = 0$ : $K (0, w) = 0$ pour tout $w$ . La colonne $w = 0$ vaut aussi 0 partout, mais c'est une conséquence de (10.1), pas un cas de base: avec une capacité nulle, aucun objet de poids strictement positif ne rentre.

L'ordre de calcul se lit sur la récurrence: $K (i, w)$ ne dépend que de cases de la ligne $i - 1$ . Il suffit donc de remplir la table ligne par ligne, par $i$ croissant; à l'intérieur d'une ligne, l'ordre des $w$ est indifférent. La table a $(n + 1) (W + 1)$ cases et chaque case coûte une comparaison et une addition: le coût est $Θ (nW)$ opérations, et la mémoire aussi.

def sac_a_dos(poids, valeurs, W):
    """Table K[i][w] = valeur maximale avec les i premiers objets, capacite w."""
    n = len(poids)
    K = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(W + 1):

Comptons: la double boucle exécute son corps $n (W + 1)$ fois, soit $4 \times 10 = 40$ fois sur l'instance du cours, et chaque exécution fait une comparaison de poids, au plus une addition et au plus une comparaison de valeurs. On ne comptera jamais plus de $2 n (W + 1)$ comparaisons — 80 ici — contre les 16 sous-ensembles de l'énumération. Sur cette instance minuscule, la table n'est pas rentable; elle le devient dès que $2^{n}$ dépasse $nW$ , c'est-à-dire très vite.

Exemple 10.1 · La table du sac à dos témoin, ligne par ligne

Exécutons le code ci-dessus sur l'instance du cours et affichons la table.

poids = [2, 3, 4, 5]
valeurs = [3, 4, 5, 8]
noms = ["A", "B", "C", "D"]
K

La reconstruction de la solution

La table donne la valeur de l'optimum. Elle ne donne pas la sélection, et c'est pourtant la sélection que l'on veut: savoir que l'on peut emporter 13 sans savoir quoi mettre dans le sac n'a aucune utilité pratique.

La reconstruction se lit dans la table, sans information supplémentaire, en remontant depuis la case $(n, W)$ . Le principe tient en une phrase: à la case $(i, w)$ , on compare $K (i, w)$ à $K (i - 1, w)$ ; si les deux sont égales, l'objet $i - 1$ n'était pas nécessaire et l'on monte tout droit; s'ils diffèrent, c'est que le maximum a été atteint par le second terme de (10.1), donc l'objet est pris et l'on recule de son poids.

def reconstruire(K, poids, W):
    """Remonte la table et renvoie les indices des objets pris."""
    i, w = len(poids), W
    choix = []
    while i > 0:
        if K[i][w] != K[i - 1][w]:     # la valeur a change: l'objet i-1 est pris
            choix.append(i - 1)
            w -= poids[i - 1]
        i -= 1
    return sorted(choix)

Ce que le glouton du chapitre 9 obtient ici

Le chapitre 9 a montré que le sac à dos fractionnaire — celui où l'on peut emporter une fraction d'objet — se résout par un glouton: on trie les objets par rapport valeur/poids décroissant et l'on remplit jusqu'au bord, le dernier objet étant coupé. L'argument d'échange y est valide, et le résultat est optimal. Sur notre instance, ce glouton fractionnaire prend $D$ (rapport 1,60), puis $A$ (1,50), et complète les 2 unités restantes avec les deux tiers de $B$ , pour une valeur de $8 + 3 + \frac{2}{3} \times 4 = \frac{41}{3} \approx 13, 67$ .

Appliquons la même règle au problème 0/1, où l'on ne coupe rien. Le glouton prend $D$ , puis $A$ — total de poids 7 —, puis constate que $B$ (poids 3) et $C$ (poids 4) ne rentrent plus dans les 2 unités qui restent. Il s'arrête sur une valeur de 11, avec deux unités de capacité perdues. L'optimum est 13. Le glouton manque l'optimum de deux unités, et il le manque justement parce qu'il a pris l'objet de meilleur rapport en premier: $D$ et $A$ laissent un trou de 2 que rien ne comble, alors que $C$ et $D$ remplissent le sac au gramme près.

def glouton_par_rapport(poids, valeurs, W):
    """Le glouton du chapitre 9, applique tel quel au sac a dos 0/1."""
    ordre = sorted(range(len(poids)), key=lambda i: valeurs[i] / poids[i], reverse=True)
    reste, total, pris = W, 0, []
    for i in ordre:
        if poids[i] <= reste:
            reste -= poids[i]
            total += valeurs[i]
            pris.append(i)

print(glouton_par_rapport([2, 3, 4, 5], [3, 4, 5, 8], 9))

(11, [0, 3])

Le glouton par rapport n'est pas le seul possible, et la comparaison des variantes est instructive. Voici ce que donnent, sur cette instance, trois règles gloutonnes classiques, le tout calculé et non deviné:

Règle gloutonne	Ordre d'examen	Sélection	Valeur
Rapport $v / p$ décroissant	$D$ , $A$ , $B$ , $C$	$A$ , $D$	11
Poids croissant	$A$ , $B$ , $C$ ,

Lisez la troisième ligne avec méfiance: sur cette instance, le glouton par valeur décroissante trouve l'optimum. Il serait absurde d'en conclure quoi que ce soit. Prenons une instance différente, explicitement distincte de celle du cours: capacité 10, trois objets de poids et valeurs $(6, 10)$ , $(5, 7)$ et $(5, 7)$ . Le glouton par valeur décroissante prend le premier, de valeur 10, et plus rien ne rentre dans les 4 unités restantes: il obtient 10. L'optimum prend les deux objets de poids 5 et vaut 14. Le glouton par valeur décroissante manque donc 4 unités sur 14, soit près de 29 % de l'optimum.

Un glouton qui réussit sur trois exemples n'est pas démontré

Ce chapitre et le précédent illustrent ensemble la règle la plus importante sur les algorithmes gloutons: un glouton se démontre ou se réfute, il ne se teste pas. Pour le sac à dos fractionnaire, l'argument d'échange du chapitre 9 est une démonstration, et l'algorithme est optimal sur toutes les instances. Pour le sac à dos 0/1, aucun ordre de tri ne donne d'algorithme glouton optimal — et le chapitre 11 dira pourquoi: ce problème est $N P$ -difficile, donc un glouton optimal en temps polynomial donnerait $P = N P$ .

Entre les deux, la différence tient à une seule hypothèse: la possibilité de couper le dernier objet. Elle suffit à rendre l'échange admissible dans un cas et inadmissible dans l'autre. Quand vous proposez un glouton, cherchez d'abord un contre-exemple; si vous n'en trouvez pas, cherchez la démonstration; et si vous n'avez ni l'un ni l'autre, vous n'avez rien.

L'explorateur ci-dessous vous laisse faire varier la capacité et le nombre d'objets disponibles. Deux réglages voisins méritent d'être comparés attentivement, parce qu'ils contiennent à eux seuls la raison pour laquelle le problème n'est pas glouton.

Explorateur 10.1 · Le sac à dos 0/1, capacité par capacité

Les quatre objets sont ceux du cours: A(2,3), B(3,4), C(4,5) et D(5,8), le premier nombre étant le poids et le second la valeur. Déplacez la capacité et regardez la dernière ligne de la table se remplir, puis la remontée changer de trajet. Comparez surtout deux réglages voisins: à W = 8 l'optimum prend B et D, à W = 9 il prend C et D — une unité de capacité de plus, et la sélection est refaite de fond en comble, pas complétée. Le dernier affichage compare l'optimum au glouton qui prend les objets par rapport valeur/poids décroissant: les deux coïncident souvent, et pas à W = 9.

Capacité W9

Objets disponibles (les k premiers)A, B, C, D

Optimum K[k][W]

Sélection

C, D

Poids utilisé

9 / 9

Cases calculées

Glouton par v/p

Écart optimum − glouton

À $W = 8$ , l'optimum vaut 12 et prend ${B, D}$ . À $W = 9$ , il vaut 13 et prend ${C, D}$ . Une unité de capacité de plus, et la solution n'est pas complétée: elle est refaite, $B$ sortant du sac pour laisser la place à $C$ . C'est exactement ce qu'un algorithme glouton ne sait pas faire — il ne revient jamais sur un choix —, et c'est ce que la table fait sans effort, puisqu'elle ne décide rien avant d'avoir tout comparé.

Question 10.3

Sur l'instance du cours, combien de cases la table du sac à dos contient-elle, cas de base compris?

Question 10.4

Écrivez la fonction qui remplit la table du sac à dos 0/1. Elle doit renvoyer la table complète, sous la forme d'une liste de lignes, et le programme affiche sa dernière ligne pour l'instance du cours. Vos vérifications appelleront ensuite votre fonction sur une seconde instance que vous n'avez jamais vue, alors n'écrivez pas la réponse en dur.

sac_a_dos.py

Question 10.5

La table donne la valeur, pas la sélection. Écrivez la remontée: partant de la case du coin, comparez chaque case à celle du dessus et renvoyez la liste triée des indices des objets pris. La fonction de remplissage vous est donnée, et vos vérifications porteront aussi sur deux instances que vous n'avez pas vues.

reconstruction.py

Deux problèmes sur les chaînes

Le sac à dos indexe ses sous-problèmes par un objet et une capacité. Les deux problèmes de cette section les indexent par deux préfixes, et cette forme-là est de très loin la plus fréquente en pratique: comparaison de fichiers, correction orthographique, alignement de séquences biologiques, reconnaissance de la parole. Toutes ces applications sont la même grille.

La plus longue sous-séquence commune

Le problème: étant données deux chaînes $X$ de longueur $m$ et $Y$ de longueur $n$ , trouver une sous-séquence commune de longueur maximale. Le nombre de sous-séquences de $X$ vaut $2^{m}$ , donc l'énumération est hors de question dès la vingtaine de caractères.

Appliquons la discipline. La case, d'abord, et la phrase qui la définit:

$C (i, j)$ est la longueur de la plus longue sous-séquence commune des préfixes $X [0 : i]$ et $Y [0 : j]$ .

La dernière décision porte sur les derniers caractères des deux préfixes, et le raisonnement est un découpe-recollage du même type qu'au théorème 10.2. Si $X [i - 1] = Y [j - 1]$ , on peut toujours supposer que ce caractère commun est apparié dans une solution optimale — s'il ne l'était pas, on pourrait l'ajouter à la fin, ce qui allongerait la sous-séquence d'une unité et contredirait l'optimalité —, et le reste est une plus longue sous-séquence commune de $X [0 : i - 1]$ et $Y [0 : j - 1]$ . S'ils diffèrent, une solution optimale n'utilise pas ou n'utilise pas — elle ne peut pas les apparier l'un à l'autre puisqu'ils sont distincts —, et l'on prend le meilleur des deux cas. D'où:

C (i, j) = ⎩ ⎨ ⎧ 0 C (i - 1, j - 1) + 1 max (C (i - 1, j), C (i, j - 1)) si i = 0 ou j = 0, si X [i - 1] = Y [j - 1], sinon. (10.2)

def lcs(X, Y):
    """Grille C[i][j] = longueur de la plus longue sous-sequence commune des prefixes."""
    m, n = len(X), len(Y)
    C = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n

Le coût est $Θ (mn)$ comparaisons de caractères, et la mémoire $Θ (mn)$ entiers. L'ordre de remplissage est celui des lignes croissantes, chaque case ne dépendant que de ses voisines du haut, de la gauche et de la diagonale haut-gauche.

Exemple 10.3 · ALGORITHME contre LOGARITHME, en entier

Les deux mots témoins de ce chapitre sont ALGORITHME et LOGARITHME, de dix lettres chacun. Ils ne diffèrent que par leurs quatre premières lettres, mais ces quatre-là sont permutées, ce qui rend le résultat moins évident qu'il n'y paraît.

C = lcs("ALGORITHME", "LOGARITHME")
print("longueur :", C[10][10])
for i, ligne in enumerate(C):
    print(("_" + "ALGORITHME")[i], ligne)

longueur : 8
_ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
A [0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1]
L [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
G [0, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2]
O [0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2]
R [0, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3]
I [0, 1, 2, 2, 2, 3, 4, 4, 4, 4, 4]
T [0, 1, 2, 2, 2, 3, 4, 5, 5, 5, 5]
H [0, 1, 2, 2, 2, 3, 4, 5, 6, 6, 6]
M [0, 1, 2, 2, 2, 3, 4, 5, 6, 7, 7]
E [0, 1, 2, 2, 2, 3, 4, 5, 6, 7, 8]

def reconstruire_lcs(C, X, Y):
    """Remonte la grille et renvoie une plus longue sous-sequence commune."""
    i, j = len(X), len(Y)
    lettres = []
    while i > 0 and j > 0:
        if X[i - 1] == Y[j - 1]:
            lettres.append(X[i - 1])
            i -= 1
            j -= 1

Question 10.6

Dans la grille de la plus longue sous-séquence commune, que signifie une case dont la valeur est égale à celle de sa voisine de gauche ET à celle de sa voisine du dessus?

La distance d'édition

La discipline, une troisième fois. La case: $D (i, j)$ est la distance d'édition entre les préfixes $X [0 : i]$ et $Y [0 : j]$ . La dernière décision: que fait-on du dernier caractère de $X [0 : i]$ ? On le supprime, on insère devant lui le dernier caractère de $Y [0 : j]$ , ou on l'apparie à ce dernier — gratuitement s'ils sont égaux, au prix d'une substitution sinon. Les cas de base ne sont plus nuls: transformer un préfixe vide en un préfixe de $j$ caractères coûte insertions.

D (i, j) = ⎩ ⎨ ⎧ j i min (D (i - 1, j) + 1, D (i, j - 1) + 1, D (i - 1, j - 1) + c_{ij}) si i = 0, si j = 0, sinon, (10.3)

où $c_{ij} = 0$ si $X [i - 1] = Y [j - 1]$ et $c_{ij} = 1$ sinon.

def distance_edition(X, Y):
    """Grille D[i][j] = distance d'edition entre les prefixes X[0:i] et Y[0:j]."""
    m, n = len(X), len(Y)
    D = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        D[i][0] = i
    for j in

Exemple 10.4 · La distance d'édition entre les deux mots témoins

D = distance_edition("ALGORITHME", "LOGARITHME")
print(D[10][10])
for i, ligne in enumerate(D):
    print(("_" + "ALGORITHME")[i], ligne)

3
_ [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
A [1, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9]
L [2, 1, 2, 3, 4, 4, 5, 6, 7, 8, 9]
G [3, 2, 2, 2, 3, 4, 5, 6, 7, 8, 9]
O [4, 3, 2, 3, 3, 4, 5, 6, 7, 8, 9]
R [5, 4, 3, 3, 4, 3, 4, 5, 6, 7, 8]
I [6, 5, 4, 4, 4, 4, 3, 4, 5, 6, 7]
T [7, 6, 5, 5, 5, 5, 4, 3, 4, 5, 6]
H [8, 7, 6, 6, 6, 6, 5, 4, 3, 4, 5]
M [9, 8, 7, 7, 7, 7, 6, 5, 4, 3, 4]
E [10, 9, 8, 8, 8, 8, 7, 6, 5, 4, 3]

La distance vaut 3, et la remontée de la grille donne trois substitutions, toutes dans les quatre premières lettres:

Position (à partir de 1)	Lettre de `ALGORITHME`

Question 10.7

Écrivez la longueur de la plus longue sous-séquence commune en ne gardant en mémoire que deux lignes de la grille: la précédente et celle en cours. Le programme affiche la longueur pour les deux mots du cours, et vos vérifications appelleront votre fonction sur des paires de mots que vous n'avez pas vues.

lcs_deux_lignes.py

L'optimisation en espace, et ce qu'elle coûte

Deux lignes suffisent pour la valeur

Regardez à nouveau la récurrence (10.1) du sac à dos: $K (i, w)$ ne dépend que de la ligne $i - 1$ . Il est donc inutile de conserver les lignes $0$ à $i - 2$ une fois la ligne $i - 1$ calculée. Deux lignes suffisent — et même une seule, à condition de la parcourir dans le bon sens.

def sac_a_dos_une_ligne(poids, valeurs, W):
    """La valeur optimale seule, en memoire O(W)."""
    L = [0] * (W + 1)
    for p, v in zip(poids, valeurs):
        for w in range(W, p - 1, -1):     # DECROISSANT: voir ci-dessous
            L[w] = max(L[w], L[w - p] + v)
    return L

print(sac_a_dos_une_ligne([2, 3, 4, 5], [3, 4, 5, 8], 9))

[0, 0, 3, 4, 5, 8, 8, 11, 12, 13]

On retrouve exactement la dernière ligne de la table: la mémoire passe de $Θ (nW)$ à $Θ (W)$ entiers, et le temps reste $Θ (nW)$ .

Le sens de la boucle intérieure n'est pas un détail de style, c'est la correction de l'algorithme. En la parcourant par $w$ décroissant, la case L[w - p] que l'on lit n'a pas encore été mise à jour pour l'objet courant: elle contient donc bien une valeur de la ligne $i - 1$ , comme (10.1) l'exige. En la parcourant par $w$ croissant, L[w - p] aurait déjà été modifiée par le même objet, et l'on autoriserait à le prendre plusieurs fois. Le résultat n'est pas «un peu faux»: c'est la réponse à un autre problème, le sac à dos non borné, où chaque objet est disponible en quantité illimitée.

def sac_non_borne(poids, valeurs, W):
    """La meme boucle en sens croissant resout le sac a dos NON BORNE."""
    L = [0] * (W + 1)
    for p, v in zip(poids, valeurs):
        for w in range(p, W + 1):
            L[w] = max(L[w], L[w - p] + v)
    return L

print(sac_non_borne([2, 3, 4, 5], [3, 4, 5, 8], 9))

[0, 0, 3, 4, 6, 8, 9, 11, 12, 14]

La valeur finale est 14 au lieu de 13, et l'on voit d'où elle vient: $D$ plus deux exemplaires de $A$ , soit $5 + 2 + 2 = 9$ de poids pour $8 + 3 + 3 = 14$ de valeur. Un seul mot changé dans une boucle, et l'algorithme répond correctement à une question qu'on ne lui a pas posée. C'est la plus jolie erreur de ce chapitre, et c'est aussi la plus difficile à repérer, parce que le résultat reste plausible: il est simplement trop grand.

Ce que l'on perd: la reconstruction

L'économie a un prix, et il est précis: avec deux lignes, on ne peut plus reconstruire la solution. La remontée de l'exemple 10.2 lit $K (i, w)$ et $K (i - 1, w)$ pour toutes les valeurs de $i$ , de $n$ jusqu'à 0; elle a donc besoin de toute la table, pas de sa dernière ligne. Le tableau ci-dessous résume l'arbitrage, et c'est lui qu'il faut avoir en tête quand on choisit:

Variante	Temps	Mémoire	Donne la valeur	Donne la sélection
Table complète	$Θ (nW)$	$Θ (nW)$	oui	oui
Deux lignes (ou une)	$Θ (nW)$	$Θ (W)$	oui	non
Diviser pour régner sur la table	$Θ (nW)$	$Θ (W)$	oui	oui

La troisième ligne mérite un mot, parce qu'elle montre que l'arbitrage n'est pas une fatalité. Pour la plus longue sous-séquence commune, l'algorithme de Hirschberg (1975) combine la réduction à deux lignes avec un diviser pour régner du chapitre 2: on calcule, en mémoire $Θ (n)$ , la colonne où la solution optimale coupe la ligne du milieu, puis on recommence récursivement sur les deux moitiés. Le temps reste $Θ (mn)$ — la somme des sous-problèmes se divise par deux à chaque niveau, et la série géométrique converge — pour une mémoire $Θ (n)$ et une reconstruction complète. Nous ne le détaillerons pas ici; retenez qu'il existe, et que la question «puis-je économiser la mémoire sans perdre la solution?» a parfois une réponse positive qui demande un peu de travail.

Question 10.8

Deux séquences d'ADN de 20 000 caractères chacune. Combien de gigaoctets faudrait-il pour stocker la grille complète de leur plus longue sous-séquence commune, à raison de 4 octets par entier? Répondez en gigaoctets, avec un giga valant 10 puissance 9 octets.

Là où la programmation dynamique ne s'applique pas

Le plus long chemin simple

Le meilleur moyen de comprendre ce que la sous-structure optimale exige est de regarder un problème qui en manque. Prenons celui-ci, en apparence très proche des plus courts chemins du chapitre 7.

Le raisonnement naturel — et faux — est le suivant: «si le plus long chemin simple de $u$ à $v$ passe par $s$ , alors il est formé du plus long chemin simple de $u$ à $s$ , suivi du plus long chemin simple de $s$ à $v$ ». C'est mot pour mot ce que l'on fait pour les plus courts chemins, où c'est vrai. Ici, c'est faux, et un graphe à quatre sommets suffit à le montrer.

Prenons le cycle à quatre sommets $q$ , $r$ , $t$ , $s$ , avec les quatre arêtes $q - r$ , $r - t$ , $t - s$ et $s - q$ . Énumérons les chemins simples, ce qui est ici une affaire de quelques lignes de programme:

De	Vers	Chemins simples	Le plus long
$q$	$t$	$q - r - t$ , $q - s - t$	2 arêtes
$q$	$r$	$q - r$ , $q - s - t - r$

La «récurrence» proposée donnerait, en décomposant le chemin de $q$ à $t$ sur le sommet intermédiaire $r$ , un plus long chemin de $3 + 3 = 6$ arêtes. Or le graphe n'a que quatre sommets: aucun chemin simple n'y dépasse 3 arêtes, et le plus long chemin simple de $q$ à $t$ en compte 2. La formule ne se trompe pas d'une unité: elle produit un nombre qui ne correspond à aucun objet du graphe.

Pourquoi le recollage échoue

La raison est visible dans le détail du contre-exemple, et elle est exactement celle que le callout du théorème 10.2 annonçait. Le plus long chemin de $q$ à $r$ est $q - s - t - r$ : il utilise les sommets $s$ et $t$ . Le plus long chemin de $r$ à $t$ est $r - q - s - t$ : il utilise $q$ et . Les recoller donnerait une promenade passant deux fois par , deux fois par : ce n'est pas un chemin simple. Le recollage n'est pas admissible.

Formulé autrement: les deux sous-problèmes ne sont pas indépendants. Résoudre le premier consomme des sommets dont le second aurait besoin. Pour rendre les sous-problèmes indépendants, il faudrait les indexer non seulement par leurs extrémités mais aussi par l'ensemble des sommets déjà utilisés — et il y a $2^{n}$ tels ensembles. C'est précisément ce que fait la programmation dynamique sur sous-ensembles (l'algorithme de Held et Karp pour le voyageur de commerce), qui résout le problème en $Θ (2^{n} n^{2})$ : exponentiel, mais bien meilleur que les $n!$ de l'énumération des permutations. La sous-structure optimale n'est pas absente dans l'absolu; elle est absente pour l'indexation naïve, et la retrouver coûte un nombre exponentiel de sous-problèmes.

La sous-structure optimale est une hypothèse, pas une formalité

Les plus courts chemins ont la sous-structure optimale; les plus longs chemins simples ne l'ont pas. Les deux problèmes se ressemblent au point qu'on peut passer de l'un à l'autre en changeant un min en max, et pourtant l'un se résout en $Θ (m + n lo g n)$ (chapitre 7) et l'autre est $N P$ -difficile (chapitre 11).

La morale est opérationnelle: avant d'écrire une table, faites la démonstration par découpe-recollage, et regardez si le recollage reste admissible. Si votre sous-problème hérite d'une contrainte du reste de la solution — des objets déjà pris, des sommets déjà visités, une ressource déjà consommée ailleurs —, c'est le signal d'alarme: vos sous-problèmes ne sont pas indépendants, et votre table, si vous l'écrivez quand même, donnera des réponses trop bonnes pour être vraies.

Question 10.9

Pourquoi la programmation dynamique résout-elle les plus courts chemins mais pas les plus longs chemins simples?

Le coût pseudo-polynomial, et le pont vers le chapitre 11

Pourquoi le produit du nombre d'objets par la capacité n'est pas polynomial

Nous avons annoncé un coût de $Θ (nW)$ pour le sac à dos, et un lecteur pressé en conclurait que le problème est résolu en temps polynomial. C'est faux, et l'erreur est assez grave pour que le chapitre s'achève dessus.

Revenons à la définition de la taille d'une instance, posée au chapitre 1: c'est la longueur de son écriture, pas la grandeur des nombres qu'elle contient. Une instance du sac à dos s'écrit avec $n$ poids, $n$ valeurs et la capacité $W$ . Écrire $W$ en binaire demande $⌊ lo g_{2} W ⌋ + 1$ bits. La taille de l'entrée est donc de l'ordre de $n lo g (max p_{i}) + n lo g (max v_{i}) + lo g W$ , c'est-à-dire , pas linéaire.

Un coût de $Θ (nW)$ est donc exponentiel en la taille de l'écriture de $W$ : doubler le nombre de chiffres de $W$ élève $W$ au carré, et le coût aussi. Une instance avec $n = 100$ objets et $W = 1 0^{9}$ — une capacité qui s'écrit avec dix chiffres — demanderait $1 0^{11}$ cases de table, et le tableau des ordres de grandeur du chapitre 1 dit ce que cela vaut: hors de portée.

Ce constat est exactement le pont vers le chapitre 11. Le problème du sac à dos 0/1, sous sa forme décisionnelle («existe-t-il une sélection de valeur au moins $V$ et de poids au plus $W$ ?»), fait partie des vingt et un problèmes dont Karp a établi la $N P$ -complétude en 1972. S'il existait un algorithme vraiment polynomial pour lui — polynomial en $n$ et en $lo g W$ —, on en déduirait $P = N P$ . La table de ce chapitre n'est donc pas un algorithme polynomial déguisé: c'est un algorithme qui exploite la petitesse des nombres, et qui perd tout son intérêt quand ils grandissent. Le chapitre 11 montrera, en revanche, qu'on peut en tirer un schéma d'approximation: en arrondissant les valeurs, on obtient une solution à $1 - ε$ près de l'optimum en temps polynomial en et .

Question 10.10

Cet exercice utilise volontairement la limite de dix secondes de l'éditeur: ce n'est pas un bogue, c'est la démonstration. Le programme résout un sac à dos de 20 objets par récursion naïve et compte ses appels — près de deux millions. Portez d'abord n à 26 et relancez pour voir l'exécution se faire tuer, puis remettez 20 et mémoïsez la fonction: le nombre d'appels doit tomber sous 20 000, et n = 26 doit alors passer sans peine.

sac_naif.py

Synthèse

La programmation dynamique s'applique lorsque deux conditions sont réunies, et elles se vérifient séparément: la sous-structure optimale — toute solution optimale contient des solutions optimales de sous-instances, ce qui se démontre par découpe-recollage — et le chevauchement des sous-problèmes — la récursion naïve résout le même sous-problème un nombre exponentiel de fois. Diviser pour régner a la première sans la seconde; le plus long chemin simple a la seconde sans la première.
La discipline précède le code: nommer la case en une phrase complète, écrire la récurrence en énumérant les choix de la dernière décision, écrire les cas de base, fixer l'ordre de calcul. La mémoïsation (descendante) garde la récursion et ne remplit que les cases atteintes; la tabulation (ascendante) supprime la récursion, la pile et son plafond, et remplit tout. Le théorème 10.1 établit que les deux rangent la même valeur dans toute case commune, pourvu que la relation de dépendance soit acyclique.
Sur Fibonacci, la version naïve fait $2 F_{n + 1} - 1$ appels, soit 242 785 pour $n = 25$ , contre 49 appels mémoïsés et 24 additions tabulées, pour 26 valeurs distinctes. C'est le plus petit exemple où le chevauchement se voit à l'œil nu.
Le se résout par la table en temps et mémoire. Sur l'instance du cours (; , , , ), la dernière ligne est et l'optimum vaut , atteint par de poids exactement 9. La se lit dans la table en : la valeur change d'une ligne à l'autre, l'objet est pris; elle ne change pas, il est laissé. Le glouton par rapport valeur/poids du chapitre 9 prend puis et s'arrête à : un glouton se démontre ou se réfute, il ne se teste pas.

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Exercice 10.1 · Rendu de monnaie

On dispose d'un nombre illimité de pièces de chaque valeur d'un système monétaire $c_{0}, c_{1}, \dots, c_{k - 1}$ , et l'on veut payer exactement une somme $S$ avec le .

Exercice 10.2 · Remplir et remonter à la main

Reprenez l'instance du cours ( $W = 9$ , objets $A (2, 3)$ , $B (3, 4)$ , $C (4, 5)$ , $D (5, 8)$ ) mais changez l'ordre des objets: rangez-les dans l'ordre $D$ , , , .

Exercice 10.3 · Le plus long sous-tableau croissant

Soit un tableau $a$ de $n$ nombres. On cherche la longueur de la plus longue sous-séquence strictement croissante de $a$ (les éléments retenus n'ont pas besoin d'être contigus).

Nommez le sous-problème. Attention: la définition naïve «la plus longue sous-séquence croissante de $a [0 : i]$ » ne mène à aucune récurrence — dites pourquoi, puis corrigez-la.
Écrivez la récurrence et donnez le coût.
Appliquez-la au tableau témoin du cours, $a = [38, 27, 43, 3, 9, 82, 10]$ .

Exercice 10.4 · Découper une barre

Une barre de métal de longueur entière $n$ peut être découpée en morceaux de longueurs entières; un morceau de longueur $ℓ$ se vend $p_{ℓ}$ . On veut maximiser la recette totale, sans limite sur le nombre de morceaux d'une longueur donnée.

Nommez le sous-problème et écrivez la récurrence.
Donnez le coût, et comparez-le au nombre de découpes possibles.
Avec les prix $p_{1} = 1$ , , , , calculez la recette maximale pour et donnez la découpe.

Exercice 10.5 · Une démonstration: le nombre de sous-problèmes borne le coût

Cet exercice demande une démonstration complète.

Soit un problème résolu par mémoïsation sur un ensemble fini $S$ de sous-problèmes, dont la relation de dépendance est acyclique, et où chaque sous-problème a au plus $d$ dépendances et coûte au plus $C$ opérations une fois les valeurs de ses dépendances connues.

Démontrez que le nombre total d'appels de la fonction mémoïsée, depuis un sous-problème initial quelconque, est au plus $∣ S ∣ (d + 1)$ , et que le coût total est en $O (∣ S ∣ (C + d))$ .

Références

Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4ᵉ éd., MIT Press — chapitre 14, «Dynamic Programming»: découpe d'une barre, sous-structure optimale et chevauchement, plus longue sous-séquence commune, et le contre-exemple du plus long chemin simple dont ce chapitre reprend la structure.
Cormen, Leiserson, Rivest & Stein, Algorithmique, 3ᵉ éd., Dunod — le chapitre 15 de cette édition, pour le vocabulaire: sous-structure optimale, mémoïsation, reconstruction.
Kleinberg & Tardos, Algorithm Design, Pearson — chapitre 6, la meilleure présentation de la méthode par «quel est le sous-problème?», avec le sac à dos, l'ordonnancement pondéré et l'alignement de séquences, y compris l'algorithme de Hirschberg en mémoire linéaire.
Dasgupta, Papadimitriou & Vazirani, Algorithms, McGraw-Hill — chapitre 6, court et net, avec la distance d'édition traitée comme problème de plus court chemin dans un graphe acyclique, un point de vue qui éclaire le théorème 10.1.
Sedgewick & Wayne, Algorithms, 4ᵉ éd., Addison-Wesley — pour les implémentations et les questions de mémoire, ainsi que la comparaison entre versions descendante et ascendante.
Bellman, Dynamic Programming, Princeton University Press, 1957 — l'ouvrage fondateur, d'une lecture aujourd'hui difficile, à consulter pour l'origine du «principe d'optimalité» et de la terminologie.

Case	$K (i, w)$	$K (i - 1, w)$	Décision	Case suivante
$(4, 9)$	13	12	différentes: $D$ est prise, on recule de 5	$(3, 4)$
$(3, 4)$	5	4	différentes: $C$ est prise, on recule de 4	$(2, 0)$
$(2, 0)$	0	0	égales: $B$ est laissée	$(1, 0)$
$(1, 0)$	0	0	égales: $A$ est laissée	$(0, 0)$