Histoire

Origine d’un adage attribué à Philippe II de Macédoine : Διαίρει καὶ βασίλευε, littéralement « divise et règne ».

Principe

Simplifier un problème en le décomposant en sous-problèmes :

• Diviser (décomposer) le problème en sous-problèmes.
• Conquérir, c’est-à-dire résoudre les sous-problèmes.
• Combiner (composer) les solutions des sous-problèmes pour obtenir la solution du problème initial.

Principe

Si les sous-problèmes sont de même nature que le problème, mais plus petits (où la taille du problème est définie par un ordre sur la taille de ses paramètres), le problème peut être défini récursivement.

Un exemple très simple : les nombres de Fibonacci

La suite $$F_n$$ est définie par une relation de récurrence :

• $$F_0 = 0$$
• $$F_1 = 0$$
• $$F_n = F_{n-1} + F_{n-2}$$

Le problème de calcul de $$F_n$$ est décomposé en deux sous-problèmes plus petits de même nature : calculer $$F_{n-1}$$ et $$F_{n-2}$$. Leur solution peut être combinée pour retourner la solution au problème initial !

Implémentation en Python

Utilisez simplement des fonctions récursives :

def fib(n: int) -> int:
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

Problème

Le problème peut présenter des sous-problèmes qui se recouvrent, c’est-à-dire que les mêmes (sous*)problèmes doivent être résolus plusieurs fois.

Illustration

Voici l’arbre d’appels de fib(5) :

fib(2) est calculé trois fois.

Conséquence

Le temps d’exécution explose. Dans le cas de fib, il est exponentiel !

Principe

Enregistrer les solutions des (sous*)problèmes dans un mémo (un dictionnaire, un tableau…) afin d’éviter les recomputations.

Utilisation d’un dictionnaire

Un dictionnaire stocke des paires $(key, value)$ et récupère la valeur associée à une clé donnée, s’il y en a une (avec une complexité moyenne de $O(1)$).

Appeler une version mémoïsée de la fonction $f$ avec l’argument $e$ fonctionne ainsi :

• Vérifier s’il existe une valeur pour la clé $e$.
• Si oui, retourner la valeur (c’est $f(e)$).
• Sinon, calculer $f(e)$.
• Stocker la nouvelle paire $(e, f(e))$ dans le dictionnaire.
• Retourner $f(e)$.

Utilisation d’un tableau

Supposons que le paramètre de $f$ est un entier, la clé précédente peut être transformée en un indice dans un tableau de valeurs (avec un accès de complexité $O(1)$).

Le programme

def fib_memo(n):
    memo = [-1 for _ in range(n + 1)]  # initialization of memo

    def fib_memo_aux(n):
        if memo[n] != -1:  # if the result has already been computed 
            return memo[n] # return it
        if n == 0:         # else compute it (see recursive version)
            result = 0
        elif n == 1:
            result = 1
        else:
            result = fib_memo_aux(n - 1) + fib_memo_aux(n - 2)
        memo[n] = result   # record the result in memo
        return result      # and return it

    return fib_memo_aux(n)

Effet sur l’arbre d’appels

Le calcul de fib-memo($n$) requiert 2n - 1 appels.

Grand succès : le temps d’exécution est maintenant linéaire en n.

Du calcul top-down au bottom-up

Interprétons les flèches comme des dépendances entre problèmes, par exemple résoudre le problème fib-memo(5) dépend des solutions aux problèmes fib-memo(4) et fib-memo(3).

Il est possible de résoudre d’abord les sous-problèmes plus petits puis de remonter l’arbre jusqu’à sa racine.

Effet sur la complexité

• La complexité temporelle ne change pas (mais le programme est plus rapide d’un facteur constant).
• La complexité spatiale change car les appels de fonction intermédiaires sont éliminés (pas d’utilisation de la pile). Elle passe de $O(n)$ à $O(1)$.

Problèmes de recherche

Il y a des choix, ce qui conduit potentiellement à plusieurs solutions.

Exemple : si le problème est de rendre 3 euros, il est possible d’utiliser une pièce de 2 euros ou non.

Problèmes d’optimisation

Un problème d’optimisation est basé sur un problème de recherche, mais chaque solution $s$ a un coût $c(s)$, où $c$ est une fonction dite de coût. Le problème d’optimisation cherche la meilleure solution au problème de recherche, c’est-à-dire la solution minimisant le coût (ou le maximisant, selon le problème).

Exemple : si le problème est de rendre 3 euros avec le nombre minimal de pièces, la meilleure solution utilise 2 pièces (une pièce de 2 euros et une pièce de 1 euro).

Principe

La condition pour appliquer les techniques précédentes à un problème d’optimisation est qu’il présente la propriété de sous-structure optimale, c’est-à-dire

• il peut être décomposé en sous-problèmes plus petits et
• les solutions optimales à ces sous-problèmes peuvent être combinées en une solution optimale au problème initial.

Exemple

Dans le cas du problème de rendu de monnaie, on veut trouver le nombre minimal de pièces nécessaires pour rendre une somme $a$.

• Décomposition : il y a le choix de prendre (1) ou non (2) une pièce donnée de valeur $v$ dans la liste des pièces possibles.
  • (1) Le sous-problème est de rendre $a - v$ avec toutes les pièces.
  • (2) Le sous-problème est de rendre $a$ avec les pièces restantes.
• Composition : supposons que les sous-problèmes retournent les solutions optimales $n_1$ et $n_2$, la solution optimale est $min(1 + n_1, n_2)$.

Principe

En cas de choix, limiter l’exploration aux alternatives les plus prometteuses. Cela élague la recherche et améliore l’efficacité.

Exemple : rendu de monnaie

• Ordonner les pièces et commencer par la pièce de plus grande valeur.
• Si possible ($v \leq a$), prendre la pièce ! Cela semble être la manière la plus efficace de diminuer $a$.

Algorithmes de programmation dynamique vs algorithmes gloutons

Ne risque-t-on pas de manquer une solution optimale qui n’utilise pas la pièce de plus grande valeur ?

• Non avec le système euro [1, 2, 5, 10, 50] : l’algorithme glouton est un bon choix, il est plus efficace que l’algorithme DP.
• Oui avec l’ancien système de la livre britannique [1, 3, 6, 12, 24, 30] : l’algorithme glouton est un très mauvais choix, il n’est pas correct !