Paradigmes algorithmiques

Rendre 6 avec des pièces de 1, 3 et 4. La méthode naturelle — prendre la plus grosse possible, recommencer — donne 4, puis 1, puis 1 : trois pièces. La solution optimale en emploie deux : 3 et 3.

Cette méthode naturelle a un nom, elle est employée partout, et elle vient de donner une réponse fausse sur un exemple de six pièces. Ce dernier chapitre prend de la hauteur sur trois manières de chercher une solution, sur ce que chacune garantit, et surtout sur ce qu'elle ne garantit pas.

L'algorithme glouton

Un algorithme glouton construit la solution par étapes, en faisant à chaque étape le choix qui paraît le meilleur sur le moment, et sans jamais revenir dessus.

Ses qualités sont évidentes : il est simple à écrire, rapide — généralement linéaire ou en $n \log n$ après un tri — et il ne consomme presque rien. Son défaut l'est moins : rien ne garantit que la suite de choix localement optimaux donne un optimum global.

Le rendu de monnaie en est l'illustration parfaite, parce qu'il montre que la réponse dépend du système de pièces. Avec l'euro — 1, 2, 5, 10, 20, 50 — le glouton est toujours optimal. Avec 1, 3, 4, il échoue dès 6. Un système où le glouton est optimal est dit canonique, et le vérifier n'est pas trivial.

D'où la règle du chapitre, qui vaut pour toute votre pratique : un algorithme glouton se prouve ou se rejette, il ne se suppose jamais. Le fait qu'il donne la bonne réponse sur les exemples testés ne dit rien — l'échec de 1, 3, 4 n'apparaît qu'à 6, et il faudrait chercher pour le trouver par hasard.

Trois gloutons célèbres sont prouvés, et le semestre en a déjà croisé un.

Dijkstra (chapitre 9) extrait le sommet non traité le plus proche et le déclare définitif. La preuve tient à la positivité des poids : aucun détour ne peut raccourcir. Changez cette hypothèse, et le glouton devient faux.

Huffman construit un code de compression en fusionnant à chaque étape les deux symboles les moins fréquents. Kruskal construit un arbre couvrant minimal en ajoutant les arêtes par poids croissant, en sautant celles qui créeraient un cycle. Les deux se démontrent, et c'est ce qui les distingue du rendu de monnaie.

Le retour sur trace

Quand le glouton échoue, la solution suivante est d'essayer, mais intelligemment.

Le retour sur trace (backtracking) explore systématiquement l'espace des solutions en construisant une solution partielle, et en revenant en arrière dès qu'elle s'avère impossible à compléter.

1fonction explorer(solutionPartielle)2    si complète alors enregistrer et retourner3    pour chaque choix possible à cette étape4        si le choix est compatible avec ce qui est déjà posé5            ajouter le choix6            explorer(solutionPartielle)7            RETIRER le choix          ← le retour sur trace proprement dit

Deux remarques rendent le procédé familier.

C'est un parcours en profondeur du chapitre 9, dans un arbre de choix qu'on ne construit jamais : chaque nœud est une solution partielle, chaque branche un choix, chaque feuille une solution complète ou une impasse. L'arbre n'existe qu'implicitement, sous forme de la pile d'appels du chapitre 1.

Et la ligne qui compte est la dernière : retirer le choix avant d'essayer le suivant. L'oublier laisse l'état pollué par la branche précédente, et c'est la faute numéro un du TD.

Ce qui rend le procédé viable est l'élagage : on abandonne une branche dès qu'elle est condamnée, sans descendre jusqu'aux feuilles. Aux huit dames — placer huit dames sur un échiquier sans qu'aucune n'en attaque une autre — l'exploration brute examinerait $64^8$, soit plus de $10^{14}$ dispositions. En plaçant une dame par colonne et en abandonnant dès qu'une attaque apparaît, on descend à quelques milliers de nœuds. L'élagage ne change pas la nature exponentielle du problème ; il déplace la limite du praticable, et cela suffit souvent.

La programmation dynamique

Le retour sur trace essaie tout. La programmation dynamique évite d'essayer deux fois la même chose — et l'on a déjà vu le procédé au chapitre 2, sous le nom de mémoïsation.

Elle s'applique quand deux conditions sont réunies, et il faut les vérifier avant de se lancer.

Sous-structure optimale : la solution optimale du problème se construit à partir des solutions optimales de ses sous-problèmes. C'est ce qui permet de composer.

Chevauchement des sous-problèmes : les mêmes sous-problèmes reviennent un grand nombre de fois. C'est ce qui rend la mémorisation rentable — et c'est ce qui distingue la programmation dynamique de « diviser pour régner » du bloc II. Le tri fusion découpe en moitiés disjointes : aucune sous-question n'est posée deux fois, donc une table ne servirait à rien.

Deux mises en œuvre, pour un même résultat.

Descendante (mémoïsation) : la récursion naturelle, plus une table consultée avant tout calcul. C'est le fibMemo du chapitre 2, et son avantage est de ne calculer que les sous-problèmes réellement atteints.

Ascendante (tabulation) : on remplit la table dans l'ordre croissant des tailles, sans récursion. Plus économe — pas de pile d'appels — mais elle calcule tout, y compris l'inutile.

Reprenons le rendu de monnaie, correctement cette fois. Soit $M[k]$ le nombre minimal de pièces pour rendre $k$ :

où $p$ parcourt les valeurs de pièces. Sur 1, 3, 4 avec $k=6$, la table donne bien 2, en retenant $M[3] + 1$ plutôt que $M[2] + 1$. Le glouton, lui, s'était engagé sur le 4 et ne pouvait plus revenir.

Les quatre paradigmes en regard

La lecture de ce tableau est la conclusion du semestre. On préfère toujours le glouton quand on peut le prouver, la programmation dynamique quand les sous-problèmes se répètent, et le retour sur trace quand rien d'autre ne s'applique — en sachant qu'on paie alors le prix exponentiel, et que l'élagage décide de la taille traitable.

Il existe une cinquième voie, hors programme mais qu'il faut connaître de nom : quand même le retour sur trace est hors de portée, on renonce à l'optimum et l'on emploie une heuristique ou un algorithme d'approximation, qui rend une solution correcte à un facteur près, en temps raisonnable. C'est la réponse pratique à la plupart des problèmes réellement difficiles.

À vous

L'exercice met les trois paradigmes sur le même problème, ce qui est la meilleure façon de les comparer.

Le rendu de monnaie d'abord : version gloutonne, puis version dynamique, puis recherche automatique du plus petit montant où les deux divergent sur un système donné. Vous retrouverez 6 pour 1, 3, 4 — et vous pourrez vérifier que le système de l'euro ne diverge jamais.

Les huit dames ensuite, en retour sur trace, avec un compteur de nœuds explorés. Vous comparerez le nombre de nœuds avec et sans élagage, sur des échiquiers de 4 à 8 cases de côté, et vous verrez la limite du praticable se déplacer.

// ── 1. Rendu de monnaie, version gloutonne ────────────────────────────────
function gloutonRendu(pieces, montant) {
  const tri = [...pieces].sort((a, b) => b - a);   // de la plus grosse
  const rendu = [];
  for (const p of tri) {
    while (montant >= p) { rendu.push(p); montant -= p; }
  }
  return montant === 0 ? rendu : null;
}

// ── 2. Rendu de monnaie, programmation dynamique ──────────────────────────
// M[k] = nombre minimal de pièces pour rendre k.
function dynamiqueRendu(pieces, montant) {
  const M = new Array(montant + 1).fill(Infinity);
  M[0] = 0;
  // ← à écrire : pour chaque k de 1 à montant, pour chaque pièce p <= k,
  //   M[k] = min(M[k], 1 + M[k - p])
  return M[montant] === Infinity ? null : M[montant];
}

// ── 3. Cherche le plus petit montant où le glouton se trompe ──────────────
function premierEcart(pieces, jusqua) {
  for (let k = 1; k <= jusqua; k++) {
    const g = gloutonRendu(pieces, k);
    const d = dynamiqueRendu(pieces, k);
    if (g !== null && d !== null && g.length !== d) {
      return { montant: k, glouton: g, gloutonN: g.length, optimal: d };
    }
  }
  return null;
}

// ── 4. Les n dames, en retour sur trace ───────────────────────────────────
function dames(n, avecElagage) {
  let solutions = 0, noeuds = 0;
  const colonnes = [];   // colonnes[i] = colonne de la dame de la ligne i

  function compatible(ligne, col) {
    for (let l = 0; l < ligne; l++) {
      const c = colonnes[l];
      if (c === col || Math.abs(c - col) === ligne - l) return false;
    }
    return true;
  }

  function explorer(ligne) {
    noeuds++;
    if (ligne === n) { solutions++; return; }
    for (let col = 0; col < n; col++) {
      // ← sans élagage on descend même sur une position attaquée, et on ne
      //   teste qu'arrivé au bout : écrivez les deux variantes.
      colonnes[ligne] = col;
      explorer(ligne + 1);
      colonnes.length = ligne;        // LE retour sur trace : retirer le choix
    }
  }

  explorer(0);
  return { solutions, noeuds };
}

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Écrivez dynamiqueRendu.
// 2. Trouvez le plus petit montant où le glouton échoue sur [1, 3, 4].
//    Vérifiez que le système de l'euro ne diverge jamais.
// 3. Complétez dames() pour comparer le nombre de nœuds avec et sans élagage.

console.log("glouton [1,3,4] pour 6 :", gloutonRendu([1, 3, 4], 6));

function gloutonRendu(pieces, montant) {
  const tri = [...pieces].sort((a, b) => b - a);
  const rendu = [];
  for (const p of tri) {
    while (montant >= p) { rendu.push(p); montant -= p; }
  }
  return montant === 0 ? rendu : null;
}

function dynamiqueRendu(pieces, montant) {
  const M = new Array(montant + 1).fill(Infinity);
  M[0] = 0;
  // Tabulation ascendante : on remplit dans l'ordre croissant, donc M[k−p]
  // est toujours déjà connu quand on en a besoin. Aucune récursion, aucune
  // pile — et surtout, on n'est engagé par aucun choix antérieur.
  for (let k = 1; k <= montant; k++) {
    for (const p of pieces) {
      if (p <= k && M[k - p] + 1 < M[k]) M[k] = M[k - p] + 1;
    }
  }
  return M[montant] === Infinity ? null : M[montant];
}

function premierEcart(pieces, jusqua) {
  for (let k = 1; k <= jusqua; k++) {
    const g = gloutonRendu(pieces, k);
    const d = dynamiqueRendu(pieces, k);
    if (g !== null && d !== null && g.length !== d) {
      return { montant: k, glouton: g, gloutonN: g.length, optimal: d };
    }
  }
  return null;
}

function dames(n, avecElagage) {
  let solutions = 0, noeuds = 0;
  const colonnes = [];

  function compatible(ligne, col) {
    for (let l = 0; l < ligne; l++) {
      const c = colonnes[l];
      if (c === col || Math.abs(c - col) === ligne - l) return false;
    }
    return true;
  }

  function explorer(ligne) {
    noeuds++;
    if (ligne === n) {
      // Sans élagage, la vérification n'a lieu qu'ici, au bout : on a
      // descendu n niveaux pour découvrir une impasse évidente dès le second.
      if (avecElagage) solutions++;
      else {
        let bon = true;
        for (let l = 1; l < n && bon; l++) if (!compatible(l, colonnes[l])) bon = false;
        if (bon) solutions++;
      }
      return;
    }
    for (let col = 0; col < n; col++) {
      // L'élagage : on abandonne la branche AVANT de descendre.
      if (avecElagage && !compatible(ligne, col)) continue;
      colonnes[ligne] = col;
      explorer(ligne + 1);
      colonnes.length = ligne;   // retirer le choix avant d'essayer le suivant
    }
  }

  explorer(0);
  return { solutions, noeuds };
}

console.log("— rendu de monnaie —");
for (const [nom, pieces] of [["1, 3, 4", [1, 3, 4]], ["euro", [1, 2, 5, 10, 20, 50]]]) {
  const e = premierEcart(pieces, 200);
  if (e) {
    console.log("   système " + nom.padEnd(20) + " : le glouton échoue dès " + e.montant +
      " -> " + e.glouton.join("+") + " (" + e.gloutonN + " pièces) contre " + e.optimal + " optimales");
  } else {
    console.log("   système " + nom.padEnd(20) + " : aucun écart jusqu'à 200 (système canonique)");
  }
}
// Le système de l'euro est canonique — le glouton y est toujours optimal, et
// cela se démontre. Le système 1, 3, 4 est juste sur 1, 2, 3, 4, 5 et faux à
// 6 : cinq cas de test consécutifs justes ne prouvent rien.

console.log("");
console.log("— les n dames : ce que l'élagage change —");
console.log("   n | solutions |  nœuds sans élagage |  nœuds avec élagage");
for (const n of [4, 5, 6, 7, 8]) {
  const sans = dames(n, false);
  const avec = dames(n, true);
  console.log("   " + n + " | " + String(avec.solutions).padStart(9) +
    " | " + String(sans.noeuds).padStart(19) +
    " | " + String(avec.noeuds).padStart(19) +
    "   (" + Math.round(sans.noeuds / avec.noeuds) + " fois moins)");
}
// Les deux versions explorent le MÊME arbre de choix et trouvent les mêmes
// solutions. La seule différence est le moment où l'on teste : au bout pour
// l'une, à chaque niveau pour l'autre. L'élagage ne rend pas le problème
// polynomial — il reste exponentiel — mais il déplace de plusieurs cases la
// limite du praticable, et c'est souvent tout ce qu'on demande.

En travaux pratiques

système {1, 3, 4}, somme 6

glouton  : 4 + 1 + 1        → 3 pièces
optimal  : 3 + 3            → 2 pièces

le glouton fonctionne sur les systèmes CANONIQUES
(euro, dollar), et pas sur un système quelconque —
et rien dans le code ne prévient

int rendu(int somme, int *pieces, int np, int *choix) {
  int *m = malloc((somme+1) * sizeof *m);
  int *utilisee = malloc((somme+1) * sizeof *utilisee);
  m[0] = 0;
  for (int s = 1; s <= somme; s++) {
      m[s] = INT_MAX;
      for (int i = 0; i < np; i++)
          if (pieces[i] <= s && m[s-pieces[i]] != INT_MAX
                            && m[s-pieces[i]] + 1 < m[s]) {
              m[s] = m[s-pieces[i]] + 1;
              utilisee[s] = pieces[i];        /* pour reconstituer */
          }
  }
  /* reconstitution, comme le tableau precedent du TP 9 */
  int s = somme, n = 0;
  while (s > 0) { choix[n++] = utilisee[s]; s -= utilisee[s]; }
  return m[somme];
}

force brute       O(n³)  : n = 10 000 → 6 min
diviser-régner    O(n log n) : n = 10 000 → 0,002 s
Kadane, linéaire  O(n)   : n = 10 000 → 0,00004 s

/* Kadane : une seule boucle, deux variables */
int max_courant = t[0], max_global = t[0];
for (int i = 1; i < n; i++) {
  max_courant = (t[i] > max_courant + t[i]) ? t[i] : max_courant + t[i];
  if (max_courant > max_global) max_global = max_courant;
}

DIVISER POUR RÉGNER
le problème se coupe en sous-problèmes INDÉPENDANTS
→ tris fusion et rapide, dichotomie, transformée de Fourier

PROGRAMMATION DYNAMIQUE
les sous-problèmes se RECOUVRENT, et l'optimum global se
compose des optimums locaux (sous-structure optimale)
→ rendu de monnaie, sac à dos, plus longue sous-séquence,
  distance d'édition

GLOUTON
un choix local optimal est PROUVÉ mener à l'optimum global
→ arbre couvrant, Huffman, Dijkstra (qui est un glouton !)

sac à dos dynamique : O(n × C), C = capacité

C = 100        : 0,0001 s
C = 10 000     : 0,01 s
C = 1 000 000  : 1,2 s

mais C s'écrit en log2(C) BITS : passer de 10^6 à 10^9
multiplie le temps par 1000 en n'ajoutant que 10 bits à l'entrée

Ce que ce semestre laisse

Dix chapitres plus tôt, la question était de passer de « comment écrire un algorithme » à « quelle structure choisir ». Le parcours a été le suivant.

La récursivité a donné le moyen de traiter des objets définis en fonction d'eux-mêmes, et la pile d'appels a montré ce que cela coûte. Diviser pour régner en a tiré une stratégie, et l'analyse des récurrences a permis de la chiffrer — jusqu'à démontrer que $n \log n$ est une limite et non une performance. Les structures linéaires ont introduit le vrai sujet du semestre : une opération n'a pas de coût en soi, elle a un coût dans une structure donnée. Les arbres ont fait passer ce coût de $n$ à $\log n$, sous condition d'équilibre. Les graphes ont montré que tout cela n'était que des cas particuliers.

Reste une idée qui traverse les cinq blocs, et c'est peut-être ce qu'il faut en garder : la plupart des gains du semestre viennent d'une meilleure organisation des données, pas d'un code plus astucieux. Le tri rapide bat le tri par insertion parce qu'il divise, pas parce qu'il compare plus vite. Un ABR bat une liste parce que sa forme élimine la moitié des candidats à chaque comparaison. Et le même parcours donne la profondeur ou la largeur selon qu'on lui donne une pile ou une file.

À retenir