∑
MathTCG
#047 / 200•Foundations•MathTCG #047 / 500•★★Peu commune•⊦Maths Discrètes•Méthode & Idée

Programmation dynamique

Période historique : 1953 (Richard Bellman)

La stratégie algorithmique découpant un problème complexe en sous-problèmes mémoïsés.

Contenu & Formulation mathématique

Principe de la démarche
Résolution ascendante ou descendante avec mémoïsation en exploitant la sous-structure optimale et les sous-problèmes chevauchants.
Champs d'application canoniques
Calcul de distance d'édition, alignement de séquences ADN (Needleman-Wunsch), plus courts chemins et apprentissage par renforcement.
V(s)=max⁡a(R(s,a)+γ∑s′P(s′∣s,a)V(s′))V(s) = \max_{a} \left( R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V(s') \right)

Genèse & Portée historique

Paradigme d'optimisation inventé par Richard Bellman reposant sur le principe d'optimalité : une politique optimale est constituée de sous-politiques optimales. Elle évite l'explosion combinatoire des calculs redondants en mémorisant les solutions des sous-problèmes dans un tableau.

Bellman raconta qu'il choisit le mot 'programmation dynamique' pour dissimuler à son supérieur militaire hostile la nature purement mathématique de ses recherches, le mot 'dynamique' sonnant prestigieux et moderne.

« Ne jamais recalculer ce que l'on a déjà pris la peine de comprendre une fois. »

Filiations & Relations conceptuelles (1)

Notion connexe#100

Diviser pour régner

Partage le découpage en sous-problèmes, mais mémorise les résultats pour éviter les recalculs.

Objet de collection MathTCG

#047
★★Peu commune
⊦

Programmation dynamique

Maths Discrètes•MÉTHODE

Principe : Résolution ascendante ou descendante avec mémoïsation en exploitant la sous-structure optimale et les sous-problèmes chevauchants.

V(s)=max⁡a(R(s,a)+γ∑s′P(s′∣s,a)V(s′))V(s) = \max_{a} \left( R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V(s') \right)
1953 (Richard Bellman)

Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Foundations.

Extension : Foundations (#047 / 200)
Numéro global MathTCG : MathTCG #047 / 500
Rareté officielle : Peu commune (★★)
Domaine théorique : Maths Discrètes
Identifiant pérenne : programmation-dynamique
Consulter mon classeurExplorer tout le recueil
AccueilClasseurCodexBoostersÉchangesProfil