Le concept de sous-problèmes superposés

Le concept de sous-problèmes superposés fait référence à une situation dans laquelle un problème peut être décomposé en sous-problèmes plus petits, mais certains de ces sous-problèmes sont résolus plusieurs fois lors de la résolution du problème initial. Cette répétition de sous-problèmes identiques est une caractéristique essentielle qui permet d'appliquer la programmation dynamique pour résoudre efficacement le problème.

Principe fondamental

Dans un problème avec des sous-problèmes superposés, la solution optimale au problème principal dépend des solutions optimales à un ensemble de sous-problèmes. Comme ces sous-problèmes sont résolus plusieurs fois, leur solution peut être stockée et réutilisée pour réduire le temps de calcul global.

Devise : "Ne calcule jamais deux fois la même chose"

Visualisation du concept

Sans superposition (Diviser pour régner)

Les sous-problèmes sont indépendants :

      Problème
      /       \
  Sous-Pb A  Sous-Pb B
     (unique)   (unique)

Exemple : Tri fusion (Merge Sort)

Avec superposition (Programmation dynamique)

Les sous-problèmes se chevauchent :

      Problème
      /       \
  Sous-Pb A  Sous-Pb B
      \       /
     Sous-Pb C (partagé)

Exemple : Fibonacci, plus court chemin

Exemple classique : La suite de Fibonacci

Superposition évidente

Fibonacci : L'exemple parfait

La suite de Fibonacci est définie par :

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) pour n ≥ 2

Pour calculer le n-ième terme, on doit calculer les termes précédents, qui sont eux-mêmes calculés à partir des termes encore plus petits.

Arbre d'appels récursifs pour F(5)

F(5)
├── F(4)
│   ├── F(3)
│   │   ├── F(2)
│   │   │   ├── F(1)
│   │   │   └── F(0)
│   │   └── F(1)
│   └── F(2)
│       ├── F(1)
│       └── F(0)
└── F(3)
    ├── F(2)
    │   ├── F(1)
    │   └── F(0)
    └── F(1)

Les sous-problèmes en orange sont calculés plusieurs fois :
F(3) : 2 fois
F(2) : 3 fois
F(1) : 5 fois
F(0) : 3 fois

Total d'appels : 15
Appels uniques : 5

Problème de la récursion naïve

Dans la version récursive naïve, le nombre d'appels croît de façon exponentielle (O(2ⁿ)). Pour n=40, cela représente des milliards d'appels !

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

# Pour n=40, environ 331 millions d'appels !
# Pour n=50, plus de 20 milliards d'appels !

Solution avec mémoisation (exploitation de la superposition)

def fibonacci_memo(n, memo={}):
    """
    Version avec mémoisation qui stocke les résultats intermédiaires
    pour éviter de recalculer les mêmes sous-problèmes
    """
    if n in memo:
        return memo[n]
    
    if n < 2:
        return n
    
    memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
    return memo[n]

# Dès que F(3) est calculé, il est stocké et réutilisé
# Complexité : O(n) temps, O(n) mémoire

Tableau des appels avec et sans optimisation

n	Appels sans mémoisation	Appels avec mémoisation	Gain
10	177	19	9×
20	21,891	39	561×
30	2,692,537	59	45,636×
40	331,160,281	79	4,191,000×
50	20,365,011,074	99	205,700,000×

Exemple 2 : Plus court chemin dans un graphe

Graphes

Plus court chemin

Pour déterminer le plus court chemin entre deux nœuds, il peut être nécessaire de résoudre plusieurs sous-problèmes similaires pour différents nœuds intermédiaires. Ces sous-problèmes se superposent naturellement.

Exemple concret : Chemin de A à D

Graphe :
A → B (5)
A → C (3)
B → C (1)
B → D (6)
C → D (2)

Question : Plus court chemin de A à D ?

Sous-problèmes :
- d(A,D) = min( d(A,B) + d(B,D), d(A,C) + d(C,D) )
- d(B,D) = min( d(B,C) + d(C,D), 6 )
- d(C,D) = 2
- d(B,C) = 1
- d(A,B) = 5
- d(A,C) = 3

Superposition : d(C,D) est utilisé à la fois dans d(A,D) et d(B,D) !

Algorithme de Floyd-Warshall : Stocke les distances entre toutes les paires de nœuds, exploitant la superposition pour réutiliser les résultats intermédiaires.

def floyd_warshall(graphe):
    """
    Algorithme de Floyd-Warshall pour les plus courts chemins entre toutes les paires
    """
    n = len(graphe)
    dist = [[float('inf')] * n for _ in range(n)]
    
    # Initialisation
    for i in range(n):
        dist[i][i] = 0
        for j in range(n):
            if graphe[i][j] != 0:
                dist[i][j] = graphe[i][j]
    
    # Programmation dynamique : exploitation des sous-problèmes superposés
    for k in range(n):  # Nœud intermédiaire
        for i in range(n):
            for j in range(n):
                # Si passer par k donne un chemin plus court
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

Exemple 3 : Plus longue sous-séquence commune (LCS)

Chaînes

LCS - Superposition évidente

Le problème de la plus longue sous-séquence commune entre deux chaînes présente de nombreux sous-problèmes superposés.

Pour deux chaînes X = "ABCBDAB" et Y = "BDCABA", la relation de récurrence est :

LCS(i, j) = 0 si i=0 ou j=0
LCS(i, j) = 1 + LCS(i-1, j-1) si X[i-1] = Y[j-1]
LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1)) sinon

Arbre d'appels montrant la superposition

LCS(4,5)  (i=4, j=5)
    ├── LCS(3,5)  (sans X[3])
    │   ├── LCS(2,5)
    │   └── LCS(3,4)
    └── LCS(4,4)  (sans Y[4])
        ├── LCS(3,4)  ← MÊME SOUS-PROBLÈME QUE CI-DESSUS !
        └── LCS(4,3)

LCS(3,4) apparaît deux fois ! Sans mémoisation, il serait calculé deux fois.

Matrice de programmation dynamique pour LCS

        B  D  C  A  B  A
      0  0  0  0  0  0  0
    A 0  0  0  0  1  1  1
    B 0  1  1  1  1  2  2
    C 0  1  1  2  2  2  2
    B 0  1  1  2  2  3  3
    D 0  1  2  2  2  3  3
    A 0  1  2  2  3  3  4
    B 0  1  2  2  3  4  4

Chaque cellule dépend des cellules voisines (i-1,j-1), (i-1,j), (i,j-1).
En remplissant la matrice de haut en bas et de gauche à droite,
chaque sous-problème n'est résolu qu'une seule fois !

Exemple 4 : Nombre de chemins dans une grille

Problème

Combien de chemins uniques de (0,0) à (m,n) en se déplaçant uniquement vers la droite ou vers le bas ?

La relation de récurrence est :

chemins(i, j) = 1 si i=0 ou j=0
chemins(i, j) = chemins(i-1, j) + chemins(i, j-1) sinon

Visualisation de la superposition pour une grille 3×3

Position (2,2)
    ├── (1,2)
    │   ├── (0,2) = 1
    │   └── (1,1)
    │       ├── (0,1) = 1
    │       └── (1,0) = 1
    └── (2,1)
        ├── (1,1) ← MÊME SOUS-PROBLÈME QUE CI-DESSUS !
        └── (2,0) = 1

(1,1) apparaît deux fois !

Sans optimisation, la complexité est exponentielle. Avec programmation dynamique, on remplit une matrice :

    1  1  1
    1  2  3
    1  3  6

Comment reconnaître des sous-problèmes superposés ?

Indices de superposition

Récursion avec répétitions : L'arbre d'appels récursifs contient les mêmes sous-arbres à plusieurs endroits.
Relation de récurrence avec "max" ou "min" : Typique des problèmes d'optimisation où plusieurs chemins mènent aux mêmes états.
Nombre limité d'états : Le nombre de paramètres qui définissent un sous-problème est petit.
Mémorisation facile : On peut identifier un sous-problème par une clé (indices, position, etc.).

Familles de problèmes avec superposition naturelle

Famille	Exemples	Paramètres des sous-problèmes
Séquences	Fibonacci, LCS, édition distance	Indices de début/fin dans les séquences
Grilles	Chemins dans une grille, robot	Coordonnées (x, y)
Graphes	Plus court chemin, Floyd-Warshall	Paires de nœuds, nœuds intermédiaires
Sacs à dos	Knapsack 0/1, subset sum	Capacité restante, objets restants
Arbres	Diamètre d'arbre, coloration	Nœuds, sous-arbres

Contre-exemple : Problèmes sans superposition

Quand n'y a-t-il PAS de superposition ?

Tous les problèmes récursifs n'ont pas des sous-problèmes superposés. L'approche "diviser pour régner" (divide and conquer) crée généralement des sous-problèmes indépendants.

Exemple : Tri fusion (Merge Sort)

tri_fusion([5,2,4,7,1,3,6,8])
├── tri_fusion([5,2,4,7])      ← Sous-problème A
│   ├── tri_fusion([5,2])
│   └── tri_fusion([4,7])
└── tri_fusion([1,3,6,8])      ← Sous-problème B (complètement indépendant de A)
    ├── tri_fusion([1,3])
    └── tri_fusion([6,8])

Aucun sous-problème n'est partagé entre les deux moitiés !

Dans le tri fusion, chaque sous-problème est unique. Il n'y a pas de gain à mémoriser les résultats car ils ne seront jamais réutilisés.

Caractéristique	Diviser pour régner	Programmation dynamique
Relation entre sous-problèmes	Indépendants	Superposés (dépendants)
Réutilisation des résultats	Aucune	Essentielle
Structure de l'arbre d'appels	Arbre binaire équilibré	Graphe acyclique orienté (DAG)
Exemples	Merge sort, Quick sort, Recherche binaire	Fibonacci, LCS, Knapsack

Exercice pratique

Identifier les sous-problèmes superposés

Niveau : Intermédiaire

Pour chacun des problèmes suivants, déterminez s'ils présentent des sous-problèmes superposés et justifiez votre réponse :

Problème A : Calcul de la factorielle n! (récursif).
Problème B : Recherche dichotomique dans un tableau trié.
Problème C : Algorithme de Dijkstra pour le plus court chemin depuis une source unique.
Problème D : Problème du voyageur de commerce (TSP) - recherche de la tournée minimale.
Problème E : Multiplication de chaînes de matrices (trouver le parenthésage optimal).

Solution commentée

Problème A - Factorielle :Pas de superposition significative.
factorielle(n) = n × factorielle(n-1). Chaque appel récursif est unique et ne se répète pas. La structure est linéaire, pas de branchement. La programmation dynamique n'apporterait aucun gain.
Problème B - Recherche dichotomique :Pas de superposition.
À chaque étape, on explore une seule moitié du tableau. Les sous-problèmes sont disjoints et indépendants. Aucune répétition.
Problème C - Dijkstra :Pas de superposition dans sa forme classique.
Dijkstra est un algorithme glouton qui traite chaque nœud une seule fois. Bien qu'il y ait des sous-problèmes (distances aux nœuds), ils ne sont pas résolus plusieurs fois. C'est différent de Floyd-Warshall qui, lui, a de la superposition.
Problème D - Voyageur de commerce (TSP) :Forte superposition.
Le TSP a une sous-structure optimale et des sous-problèmes superposés. La solution pour un ensemble de villes S se terminant à une ville j utilise les solutions pour S\{j}. Les mêmes sous-ensembles apparaissent dans de nombreux chemins différents. C'est pourquoi la programmation dynamique (algorithme de Held-Karp) est utilisée pour les petites instances (O(n²2ⁿ)).
```
# État : (masque de villes visitées, dernière ville)
# Les mêmes sous-ensembles sont réutilisés pour différentes dernières villes
```
Problème E - Multiplication de chaînes de matrices :Forte superposition.
Pour trouver le parenthésage optimal de matrices A₁×A₂×...×Aₙ, les sous-problèmes consistent à multiplier des sous-chaînes Aᵢ...Aⱼ. Les mêmes sous-chaînes apparaissent dans différents parenthésages. C'est un exemple classique de programmation dynamique avec superposition.
```
# m[i,j] = min(m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j]) pour i ≤ k < j
# Les mêmes intervalles [i,k] et [k+1,j] sont réutilisés
```

Résumé :

Superposition : TSP, multiplication de matrices, Fibonacci, LCS, Floyd-Warshall
Pas de superposition : Factorielle, recherche dichotomique, Dijkstra, tri fusion

Points clés à retenir

Les sous-problèmes superposés sont une caractéristique essentielle des problèmes qui peuvent être résolus efficacement par programmation dynamique.
La superposition signifie que le même sous-problème est résolu plusieurs fois dans l'algorithme récursif naïf.
L'exemple classique est Fibonacci : F(3) est calculé plusieurs fois dans le calcul de F(5).
La programmation dynamique exploite la superposition en stockant les résultats des sous-problèmes pour les réutiliser (mémoisation ou tabulation).
La superposition transforme une complexité exponentielle en complexité polynomiale.
Les problèmes de type diviser pour régner (tri fusion, recherche dichotomique) n'ont généralement pas de superposition.
Pour identifier la superposition, dessinez l'arbre d'appels récursifs et cherchez les sous-arbres identiques.
La superposition combinée à la sous-structure optimale (vue dans le cours précédent) donne les deux conditions nécessaires pour appliquer la programmation dynamique.

Le concept de sous-problèmes superposés