Le concept de sous-structure optimale

Le concept de sous-structure optimale fait référence à une propriété des problèmes d'optimisation où une solution optimale du problème global peut être construite à partir de solutions optimales de ses sous-problèmes. Cette propriété est essentielle pour appliquer la programmation dynamique et les algorithmes gloutons.

Principe fondamental

Lorsqu'un problème présente une sous-structure optimale, cela signifie que les solutions optimales aux sous-problèmes locaux peuvent être combinées pour former la solution optimale au problème principal. Cette propriété permet de décomposer le problème initial en sous-problèmes plus petits et plus faciles à résoudre.

La sous-structure optimale est un indicateur clé pour utiliser la programmation dynamique ou les algorithmes gloutons comme approche de résolution. Dans le cas de la programmation dynamique, les solutions aux sous-problèmes sont stockées et utilisées pour résoudre des problèmes plus grands, tandis que les algorithmes gloutons construisent une solution globale en prenant des décisions optimales à chaque étape locale.

Visualisation du concept

Problème global P
        │
        ├── Sous-problème P₁ (solution optimale S₁)
        ├── Sous-problème P₂ (solution optimale S₂)
        ├── Sous-problème P₃ (solution optimale S₃)
        └── ...

        ↓
Solution optimale de P = Combinaison(S₁, S₂, S₃, ...)

Figure : La solution optimale du problème global est construite à partir des solutions optimales des sous-problèmes

Pourquoi la sous-structure optimale est-elle importante ?

Identification de la méthode

La présence d'une sous-structure optimale indique qu'on peut utiliser :

Programmation dynamique : si les sous-problèmes se chevauchent
Algorithmes gloutons : si le choix local optimal mène à la solution globale

Réduction de complexité

Permet de décomposer un problème complexe en sous-problèmes plus simples, réduisant souvent la complexité de exponentielle à polynomiale.

Réutilisabilité

Les solutions des sous-problèmes peuvent être réutilisées plusieurs fois, évitant les calculs redondants.

Exemples de problèmes avec sous-structure optimale

1. Problème du plus court chemin

Graphes

Plus court chemin

La solution optimale pour le plus court chemin entre deux nœuds dans un graphe peut être obtenue en trouvant les plus courts chemins pour des nœuds intermédiaires.

Propriété de sous-structure optimale : Si le chemin le plus court de A à C passe par B, alors la sous-partie de A à B est elle-même le plus court chemin de A à B.

Soit d(u,v) la distance la plus courte entre u et v.
Si le chemin optimal de u à v passe par w, alors :
d(u,v) = d(u,w) + d(w,v)

Algorithmes exploitant cette propriété :

Algorithme de Floyd-Warshall (programmation dynamique)
Algorithme de Dijkstra (glouton pour graphes sans poids négatifs)
Algorithme de Bellman-Ford (programmation dynamique)

2. Problème de la plus longue sous-séquence commune (PLSC)

Chaînes

Plus longue sous-séquence commune (LCS)

La solution optimale pour trouver la plus longue sous-séquence commune entre deux séquences peut être obtenue en résolvant des sous-problèmes plus petits, tels que les plus longues sous-séquences communes entre des sous-séquences plus courtes.

Propriété de sous-structure optimale : Soient X = <x₁, x₂, ..., xₘ> et Y = <y₁, y₂, ..., yₙ> deux séquences, et Z = <z₁, z₂, ..., zₖ> une LCS de X et Y.

Si xₘ = yₙ, alors zₖ = xₘ = yₙ et Zₖ₋₁ est une LCS de Xₘ₋₁ et Yₙ₋₁.
Si xₘ ≠ yₙ, alors zₖ ≠ xₘ implique que Z est une LCS de Xₘ₋₁ et Y.
Si xₘ ≠ yₙ, alors zₖ ≠ yₙ implique que Z est une LCS de X et Yₙ₋₁.

Implémentation récursive avec mémoisation :

def lcs_memo(X, Y, i, j, memo):
    """
    Calcule la longueur de la plus longue sous-séquence commune
    Version avec mémoisation
    """
    if (i, j) in memo:
        return memo[(i, j)]
    
    if i == 0 or j == 0:
        resultat = 0
    elif X[i-1] == Y[j-1]:
        resultat = 1 + lcs_memo(X, Y, i-1, j-1, memo)
    else:
        resultat = max(lcs_memo(X, Y, i-1, j, memo),
                       lcs_memo(X, Y, i, j-1, memo))
    
    memo[(i, j)] = resultat
    return resultat

# Test
X = "ABCBDAB"
Y = "BDCABA"
memo = {}
print(f"Longueur LCS : {lcs_memo(X, Y, len(X), len(Y), memo)}")  # 4 (BCBA ou BDAB)

3. Problème du sac à dos (Knapsack)

Optimisation

Sac à dos (Knapsack)

Pour déterminer la combinaison d'objets qui maximise la valeur totale sans dépasser la capacité du sac à dos, la solution optimale peut être construite à partir de solutions optimales pour des sous-problèmes avec des capacités réduites ou moins d'objets disponibles.

Propriété de sous-structure optimale : Soit K(w, j) la valeur maximale atteignable avec une capacité w en considérant les j premiers objets.

K(w, j) = max( K(w, j-1), valeurs[j-1] + K(w - poids[j-1], j-1) )
où le premier terme correspond à ne pas prendre l'objet j, et le second à le prendre (si son poids ≤ w).

Implémentation par programmation dynamique :

def knapsack_dp(poids, valeurs, capacite):
    """
    Résout le problème du sac à dos par programmation dynamique
    """
    n = len(poids)
    
    # Tableau dp[i][w] = valeur max avec i objets et capacité w
    dp = [[0] * (capacite + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, capacite + 1):
            if poids[i-1] <= w:
                # On peut prendre l'objet i-1
                dp[i][w] = max(
                    valeurs[i-1] + dp[i-1][w - poids[i-1]],
                    dp[i-1][w]
                )
            else:
                # L'objet est trop lourd
                dp[i][w] = dp[i-1][w]
    
    return dp[n][capacite]

# Test
poids = [2, 3, 4, 5]
valeurs = [3, 4, 5, 6]
capacite = 5
print(f"Valeur maximale: {knapsack_dp(poids, valeurs, capacite)}")  # 7

4. Problème de l'arbre couvrant de poids minimum (MST)

Graphes

Arbre couvrant minimum (MST)

Pour construire un arbre couvrant de poids minimum d'un graphe, il est possible de combiner des sous-arbres couvrant de poids minimum pour former la solution optimale globale.

Propriété de sous-structure optimale (propriété de coupe) : Pour toute coupe du graphe, l'arête de poids minimum traversant cette coupe appartient à un arbre couvrant minimum.

Algorithmes exploitant cette propriété :

Algorithme de Kruskal (glouton) : trie les arêtes par poids et ajoute la plus petite arête qui ne crée pas de cycle.
Algorithme de Prim (glouton) : construit l'arbre en ajoutant à chaque étape la plus petite arête connectant un nœud de l'arbre à un nœud extérieur.

5. Problème de rendu de monnaie

Monnaie

Rendu de monnaie

Étant donné un ensemble de pièces et un montant à rendre, trouver le nombre minimum de pièces nécessaire.

Propriété de sous-structure optimale : Si une solution optimale pour un montant M utilise une pièce de valeur v, alors le reste de la solution est optimal pour le montant M-v.

Implémentation récursive avec mémoisation :

def rendu_monnaie_memo(montant, pieces, memo):
    """
    Trouve le nombre minimum de pièces pour rendre un montant
    """
    if montant in memo:
        return memo[montant]
    
    if montant == 0:
        return 0
    
    min_pieces = float('inf')
    for piece in pieces:
        if piece <= montant:
            nb_pieces = 1 + rendu_monnaie_memo(montant - piece, pieces, memo)
            min_pieces = min(min_pieces, nb_pieces)
    
    memo[montant] = min_pieces
    return min_pieces

pieces = [1, 2, 5, 10, 20, 50]
montant = 63
memo = {}
print(f"Minimum de pièces pour {montant}: {rendu_monnaie_memo(montant, pieces, memo)}")

Contre-exemple : Problèmes sans sous-structure optimale

Important : Tous les problèmes n'ont pas cette propriété

Il est crucial de comprendre que certains problèmes ne présentent PAS de sous-structure optimale. Dans ces cas, ni la programmation dynamique ni les algorithmes gloutons ne peuvent garantir une solution optimale.

Exemple : Le plus long chemin simple dans un graphe

Dans un graphe général (non orienté et sans cycles), trouver le plus long chemin simple entre deux sommets n'a pas de sous-structure optimale. Pourquoi ?

Problème : Le sous-chemin d'un plus long chemin n'est pas nécessairement un plus long chemin entre ses extrémités.

    A --- B
    |     |
    C --- D

Plus long chemin de A à D : A-B-D (longueur 2)
Sous-chemin A-B : longueur 1
Mais le plus long chemin de A à B est A-C-D-B (longueur 3)

Le sous-chemin A-B du chemin optimal A-B-D n'est PAS optimal pour aller de A à B. Donc la sous-structure optimale n'est pas vérifiée.

Tableau récapitulatif des exemples

Problème	Sous-structure optimale ?	Programmation dynamique	Algorithme glouton
Plus court chemin	Oui	Floyd-Warshall, Bellman-Ford	Dijkstra (sans poids négatifs)
Plus longue sous-séquence commune	Oui	Algorithmes LCS	Non (le choix local ne mène pas à l'optimum)
Sac à dos (0/1)	Oui	Programmation dynamique classique	Non (sauf version fractionnaire)
Arbre couvrant minimum	Oui	Peut être résolu par PD (moins efficace)	Kruskal, Prim
Rendu de monnaie	Oui	Programmation dynamique	Non (sauf systèmes canoniques)
Plus long chemin simple	Non	Impossible (NP-difficile)	Impossible
Voyageur de commerce (TSP)	Non (ou partielle)	Possible mais exponentiel (Held-Karp)	Heuristiques uniquement

Programmation dynamique vs Algorithmes gloutons

Les deux approches exploitent la sous-structure optimale, mais de manière différente :

Critère	Programmation dynamique	Algorithmes gloutons
Approche	Considère toutes les possibilités, stocke les résultats intermédiaires	Prend une décision locale optimale à chaque étape
Utilisation de la sous-structure	Combine les solutions optimales des sous-problèmes	Suppose que le choix local optimal mène à l'optimum global
Quand l'utiliser	Quand les sous-problèmes se chevauchent et que le choix local optimal n'est pas suffisant	Quand la propriété de choix glouton est vérifiée (le choix local mène à l'optimum global)
Complexité	Souvent polynomiale mais peut être plus élevée	Généralement très efficace (souvent O(n log n) ou moins)
Exemples	LCS, sac à dos 0/1, Floyd-Warshall	Dijkstra, Kruskal, rendu de monnaie (systèmes canoniques)

Comment vérifier si un problème a une sous-structure optimale ?

Méthodologie

Décomposer le problème : Identifier les sous-problèmes naturels.
Formuler une relation de récurrence : Exprimer la solution optimale en fonction des solutions des sous-problèmes.
Preuve par l'absurde : Montrer que si un sous-problème n'était pas résolu de façon optimale, on pourrait améliorer la solution globale.
Tester sur des petits exemples : Vérifier que la propriété tient pour des cas concrets.

Exemple de vérification pour le plus court chemin :

Preuve : Supposons que le plus court chemin de u à v est u → ... → w → ... → v. Si le sous-chemin de u à w n'était pas optimal, il existerait un chemin plus court de u à w. En remplaçant la sous-partie, on obtiendrait un chemin plus court de u à v, ce qui contredit l'optimalité du chemin original. Donc le sous-chemin doit être optimal.

Exercice pratique

Analyse de sous-structure optimale

Niveau : Intermédiaire

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

Problème A : Trouver le chemin le plus long (en nombre d'arêtes) dans un arbre (graphe acyclique).
Problème B : Trouver la somme maximale d'un sous-tableau contigu (problème de Kadane).
Problème C : Ordonnancement de tâches avec deadlines pour maximiser le nombre de tâches accomplies.
Problème D : Coloration de graphe avec un nombre minimum de couleurs.

Solution commentée

Problème A - Plus long chemin dans un arbre :Oui, sous-structure optimale.
Dans un arbre, le plus long chemin (diamètre) peut être construit à partir des plus longs chemins dans les sous-arbres. On peut résoudre ce problème par programmation dynamique (deux parcours DFS).
Problème B - Sous-tableau contigu de somme maximale :Oui, sous-structure optimale.
La solution optimale pour une séquence de longueur i peut être construite à partir de la solution optimale pour i-1. C'est la base de l'algorithme de Kadane (programmation dynamique).
```
# Relation de récurrence :
# max_ending_here[i] = max(tableau[i], max_ending_here[i-1] + tableau[i])
```
Problème C - Ordonnancement avec deadlines :Oui, sous-structure optimale.
Ce problème peut être résolu par un algorithme glouton (trier par deadline ou par profit). La propriété de choix glouton est vérifiée, et la sous-structure optimale permet de construire la solution étape par étape.
Problème D - Coloration de graphe (minimum) :Non, pas de sous-structure optimale simple.
Le problème de coloration minimale est NP-difficile. La couleur choisie pour un sommet affecte globalement toutes les possibilités futures, et on ne peut pas simplement combiner des solutions locales optimales pour obtenir une solution globale optimale.

Points clés à retenir

La sous-structure optimale est une propriété fondamentale pour appliquer programmation dynamique et algorithmes gloutons.
Un problème a une sous-structure optimale si une solution optimale globale contient des solutions optimales à ses sous-problèmes.
Cette propriété permet de décomposer le problème et de réutiliser les solutions des sous-problèmes.
La programmation dynamique utilise cette propriété en combinant toutes les solutions optimales des sous-problèmes.
Les algorithmes gloutons utilisent une version plus forte : le choix local optimal mène à l'optimum global.
Des problèmes classiques comme le plus court chemin, la LCS, le sac à dos, et le MST possèdent cette propriété.
Le plus long chemin dans un graphe général ou la coloration de graphe n'ont pas cette propriété.
Identifier la sous-structure optimale est la première étape pour concevoir un algorithme efficace.

Le concept de sous-structure optimale