Programmation Visual Basic

Programmation dynamique : principes fondamentaux et domaines d'application

La programmation dynamique (PD) est une technique algorithmique qui résout les problèmes d'optimisation en les découpant en sous-problèmes plus petits et se chevauchant, chaque sous-problème n'étant résolu qu'une fois, ses résultats étant mémorisés pour éviter les recalculs. Elle s'épanouit sur les problèmes à sous-structure optimale et sous-problèmes qui se chevauchent.

Les principes clés

1. Sous-structure optimale

Un problème la possède si sa solution optimale se construit à partir des solutions optimales de ses sous-problèmes. Exemple : tout sous-chemin d'un plus court chemin entre deux villes est lui-même un plus court chemin.

2. Sous-problèmes qui se chevauchent

Le même sous-problème revient à plusieurs reprises. Le calcul récursif naïf de Fibonacci recalcule par exemple fib(3) plusieurs fois lors du calcul de fib(5).

3. Mémoïsation ou tabulation

La mémoïsation (haut-bas) décompose récursivement le problème et stocke chaque résultat (dans un dictionnaire ou une table de hachage) pour éviter les recalculs. La tabulation (bas-haut) calcule systématiquement tous les sous-problèmes, des plus petits au plus grand, en général dans un tableau.

4. État et transitions

Un état représente une configuration du problème ; bien le définir conditionne toute la solution, et son nombre détermine la complexité spatiale. Dans le sac à dos, un état peut être « (index, capacité) ». Les transitions décrivent comment calculer un état à partir des sous-problèmes, souvent sous forme d'équations récursives (par exemple fib(n) = fib(n-1) + fib(n-2)).

Les domaines d'application

Optimisation

  • Chemins les plus courts : Floyd-Warshall (toutes paires) et Bellman-Ford (gère les poids négatifs).
  • Sac à dos : versions 0/1, illimitée et fractionnaire.
  • Plus longue sous-séquence commune (LCS) : bio-informatique, comparaison de fichiers, édition de texte.
  • Multiplication de chaînes de matrices : ordre optimal pour minimiser les multiplications scalaires.
  • Distance de Levenshtein : correcteurs orthographiques, séquençage d'ADN, TALN.
  • Rendu de monnaie : nombre minimal de pièces ou nombre de façons d'atteindre un montant.
  • Voyageur de commerce (Held-Karp) : solution exacte pour petites instances, impraticable au-delà (NP-difficile).

Analyse de séquences

Alignement d'ADN ou de protéines (Needleman-Wunsch global, Smith-Waterman local) et modèles de Markov cachés (algorithme de Viterbi pour la séquence d'états la plus probable).

Graphes, jeux et au-delà

Flots réseau maximaux ; stratégies optimales de jeux (Minimax avec élagage alpha-bêta) ; segmentation d'images ; justification de texte et césure ; contrôle optimal des systèmes.

Mémoïsation ou tabulation ?

  • Mémoïsation : plus intuitive, ne calcule que le nécessaire, mais risque le dépassement de pile en récursion profonde.
  • Tabulation : meilleure sur les facteurs constants (pas de surcharge de récursion), mais peut calculer des sous-problèmes inutiles et exige un ordre rigoureux.

La recette pour résoudre un problème de PD

  1. Définir l'état qui identifie un sous-problème.
  2. Établir les transitions vers les sous-problèmes plus petits.
  3. Poser les cas de base.
  4. Choisir mémoïsation ou tabulation pour calculer et stocker.
  5. Déterminer l'ordre de calcul (tabulation).
  6. Extraire la solution optimale depuis les résultats stockés.

Puissante mais exigeante, la programmation dynamique demande une analyse soignée et une conception propre à chaque problème. La maîtrise vient avec la pratique.

Article précédent:
Article suivant: No
Articles recommandés