Introduction à la programmation dynamique

Supposons que nous ayons un système économique S dont les états à tout moment t sont spécifiés par un vecteur P au cours du temps, ce système est sujet aux changements d'origine soit déterministe, soit stochastique, ce qui signifie mathématiquement que les variables décrivant le système subit des transformations.

Supposons maintenant que nous avons un processus qui peut être appliqué au système à tout moment. Un processus de ce type est appelé processus de décision, avec une décision équivalente à une transformation.

Si nous devons prendre une décision en une seule étape, nous appelons le processus un processus en une seule étape ; si une séquence de décision, nous utilisons le terme processus de décision en plusieurs étapes,

Il existe un certain nombre de processus en plusieurs étapes dans l’étude du contrôle optimal des stocks, ou dans l’analyse entrée-sortie d’un ensemble d’industries interdépendantes, dans la planification des patients ou dans le cadre de politiques d’investissement, ou en test séquentiel ...,

L’approche classique que nous pouvons qualifier « énumérative » chaque décision peut être considérée comme le choix d’un certain nombre de variables, qui détermine les transformations à employer ; chaque séquence de choix ou de politique est un choix d’un ensemble de variables ; en regroupant tous ces choix, nous réduisons le problème à un problème classique consistant à déterminer le maximum d'une fonction donnée,

Dans la formulation classique, nous considérons l’ensemble du processus de décision en plusieurs étapes comme une étape au lieu d’augmenter considérablement la dimension du problème. Ainsi, si nous avons un processus en N étapes où il faut prendre M décisions à chaque étape, l'approche classique envisage un processus à une étape MN-dimensionnel

Cependant, « Dynamique » indique que nous nous intéressons aux processus dans lesquels le temps joue un rôle important et dans lesquels l’ordre des opérations peut être crucial. Cependant, une caractéristique essentielle de notre approche sera la réinterprétation de nombreux processus statiques sous forme dynamique. Processus dans lesquels le temps peut être introduit artificiellement.

La programmation dynamique est une technique efficace pour résoudre des problèmes d'optimisation. Il est basé sur la décomposition du problème initial en problèmes plus simples et la résolution de ces sous-problèmes à partir des plus simples. Le but du programmation dynamique est de trouver un objet optimal à partir d'un ensemble donné d'objets.

La programmation dynamique est un paradigme algorithmique qui résout un problème complexe en le divisant en sous-problèmes et stocke les résultats des sous-problèmes pour éviter de calculer à nouveau les mêmes résultats. Voici les deux propriétés principales d’un problème suggérant qu’il peut être résolu à l’aide de la programmation dynamique.

• Chevauchement de sous-problèmes
• Sous-structure optimale

Comme diviser pour régner, la programmation dynamique combine des solutions à des sous-problèmes. La programmation dynamique est principalement utilisée lorsque des solutions des mêmes sous-problèmes sont nécessaires à plusieurs reprises. Dans la programmation dynamique, les solutions calculées aux sous-problèmes sont stockées dans une table de sorte qu'elles ne doivent pas être recalculées. Par conséquent, la programmation dynamique n'est pas utile lorsqu'il n'y a pas de sous-problèmes communs (qui se chevauchent) parce qu'il n'y a pas de raison de stocker les solutions si elles ne sont pas nécessaires à nouveau. Par exemple, la recherche dichotomique n’a pas de sous-problèmes communs. Si nous prenons un exemplede suite d Fibonacci, il y a beaucoup de sous-problèmes qui sont résolus encore et encore.

Nous pouvons voir que la fonction Fib(3) est appelé 2 fois. Si nous avions stocké la valeur de Fib(3), alors au lieu de la calculer à nouveau, nous aurions pu réutiliser l'ancienne valeur stockée. Il y a deux façons différentes de stocker les valeurs pour que ces valeurs puissent être réutilisées :

• Mémoïsation (du haut vers le bas)
• Tabulation (de bas en haut)

Le programme mémoisé pour un problème est similaire à la version récursive avec une petite modification qui consiste à regarder dans un dictionnaire avant de calculer la solution. Nous créons un dictionnaire vide. Chaque fois que nous avons besoin de la solution à un sous-problème, nous examinons d’abord le dictionnaire. Si la valeur précalculée est là, nous renvoyons cette valeur. Sinon, nous calculons la valeur et plaçons le résultat dans le dictionnaire afin qu'il puisse être réutilisé ultérieurement.

Voici la version mémoisée du nième terme de Fibonacci

def fib(n, memo):

    if n == 0 or n == 1:
        memo[n] = n

    if n not in memo:
        memo[n] = fib(n-1, memo) + fib(n-2, memo)

    return memo[n]

D = {}
print(fib(6, D))

Le programme tabulé pour un problème donné crée une table de manière ascendante et renvoie la dernière entrée de la table. Par exemple, pour le même nombre de Fibonacci, nous calculons d’abord Fib(0) puis Fib(1) puis Fib(2) puis Fib(3) et ainsi de suite. Nous construisons donc littéralement les solutions de sous-problèmes ascendantes.
Voici la version tabulée du nième terme de Fibonacci

def fib(n):
    f = [0]*(n)
    f[0] = 1
    f[1] = 1

    for i in range(2, n):
        f[i] = f[i-1] + f[i-2]
        
    return f[n-1]

Si le problème initial nécessite la résolution de tous les sous-problèmes, la tabulation est généralement plus performante que la mémoïsation par un facteur constant. En effet, la tabulation ne nécessite pas de temps supplémentaire pour la récursivité et peut utiliser un tableau préalloué plutôt qu’un dictionnaire.

Si seulement certains des sous-problèmes doivent être résolus pour que le problème initial soit résolu, la mémoïsation est préférable car les sous-problèmes sont résolus paresseusement, c’est-à-dire que les calculs nécessaires sont effectués.

Un problème donné a une propriété de sous-structure optimale si une solution optimale du problème donné peut être obtenue par des solutions optimales de ses sous-problèmes.

Par exemple, le problème du plus court chemin a la propriété de sous-structure optimale suivante : Si un nœud x se trouve dans le plus court chemin d'un nœud source u à un nœud de destination v, le plus court chemin de u à v est la combinaison du plus court chemin de u à x et du plus court chemin de x à v. Les algorithmes standard comme Floyd-Warshall et Bellman-Ford sont des exemples typiques de la programmation dynamique.

En revanche, le problème du chemin le plus long n’a pas la propriété sous-structure optimale. Par chemin le plus long, nous entendons le chemin le plus long (chemin sans cycle) entre deux nœuds.

Considérons le graphe non pondéré suivant donné dans le livre « Algorithmique » de Leiserson. Il existe deux chemins les plus longs allant de q à t : q → r → t et q → s → t. Contrairement aux chemins les plus courts, ces chemins les plus longs ne possèdent pas la propriété de sous-structure optimale. Par exemple, le plus long chemin q → r → t n'est pas une combinaison du plus long chemin de q à r et du plus long chemin de r à t, car le plus long chemin de q à r est q → s → t → r et le plus long chemin de r à t est r → q → s → t.

Le développement d’un algorithme de programmation dynamique se devise en quatre étapes :

1. Identifiez s'il s'agit d'un problème de programmation dynamique
2. Identifiez les variables du problème
3. Exprimer clairement la relation de récurrence
4. Faire la tabulation (ou ajouter une mémoisation)

En règle générale, la programmation dynamique permet de résoudre tous les problèmes nécessitant de maximiser ou de minimiser certaines quantités ou les problèmes de dénombrement nécessitant de compter les arrangements dans certaines conditions ou avec certains problèmes de probabilité.

Tous les problèmes de programmation dynamique satisfont la propriété de sous-problèmes qui se chevauchent et la plupart des problèmes dynamiques classiques satisfont également à la propriété de sous-structure optimale. Une fois que nous observons ces propriétés dans un problème donné, assurez-vous qu’il peut être résolu en utilisant la programmation dynamique,

Dans notre exemple, le problème consiste à calculer le plus cours chemin entre la source S et la destination D. Ce problème a les deux propriétés : Chevauchement de sous-problèmes et Sous-structure optimale donc c’est un problème de programmation dynamique

• Chevauchement de sous-problèmes : deux appels au plus court chemin à partir du noeud 9, une à partir du noeud 6 et l’autre du noeud 7
• Sous-structure optimale : le nœud 7 se trouve dans le plus court chemin du nœud 1 à un nœud de destination 12, le plus court chemin de 1 à 12 est la combinaison du plus court chemin de 1 à 7 et du plus court chemin de 7 à 12

Nous avons maintenant établi qu’il existe une structure récursive entre les sous-problèmes. Ensuite, nous devons exprimer le problème en terme de paramètres de fonction et voir lesquels de ces paramètres changent.

Une façon de déterminer le nombre de paramètres changeants est d'énumérer des exemples de plusieurs sous-problèmes et de comparer les paramètres. Compter le nombre de paramètres changeants est précieux pour déterminer le nombre de sous-problèmes que nous devons résoudre. Il est également important pour nous aider à renforcer la compréhension de la relation de récurrence de l'étape 1.

Dans notre exemple, les deux paramètres susceptibles de changer pour chaque sous-problème sont :

• Cout minimum du nœud x au nœud D
• Prochaine nœud dans le chemin le plus court entre le nœud x et le nœud D

C'est une étape important. Exprimer la relation de récurrence aussi clairement que possible renforcera la compréhension de votre problème et facilitera considérablement le reste.

Une fois que vous avez déterminé que la relation de récurrence existe et que vous avez spécifié les problèmes en terme de paramètres, cela devrait être une étape naturelle. Comment les problèmes se rapportent-ils ? En d’autres termes, supposons que vous avez calculé les sous-problèmes. Comment calculeriez-vous le problème principal ?

Voici comment nous y pensons dans notre exemple :

Pour calculer le plus court chemin entre le nœud 6 et le nœud 12(D) il faut récupérer le minimum du cout entre les nœuds voisins de 6 dans le chemin vers le nœud 12 (9,10) donc on peut représenter formellement cette relation comme suit :

Cout(6)=Min{poids(6-9) + Cout(9), poids(6-10) + Cout(10)}

en générale :

Cout(i)=Min _{l=nœuds voisins} { poids(i, l) + cout(l) }

C’est l’étape la plus simple, consiste à commencer le calcule à partir du destination(D) et remonté dans le graph jusqu'à le nœud source (S)

Donc le cout du plus court chemin allant du nœud 1 (S) au nœud 12(D) est 16 en partant soit de 2 ou de 3

1. 1->2->7->10->12
2. 1->3->6->10->12

La complexité de cette algorithme est O(n²) dans un graph complet ou n est le nombre de nœuds

Comme vous voyez au cours de résolution du problème on a 5 étapes et dans chaque étape il faut prendre une décision pour le chemin optimal à suivre d’ou le nom de graphe en plusieurs étapes et c’est l’idée générale de la programmation dynamique

import math

class Graphe():

    def __init__(self, noeuds, couts):
        self.matriceAdj = noeuds.copy()
        self.couts = couts
        self.n = len(matriceAdj)

    # calculer le cout minimum entre le Noeud noeud et la destination
    def cout(self, noeud):
        # initialiser le cout et le prochaine noeud dans le chemin
        min = math.inf
        suiv = None

        # pour chaque voisin de noeud calculer le cout
        for j in range(self.n):
            if self.matriceAdj[noeud][j] > 0:
                val = self.matriceAdj[noeud][j]+self.couts[j][0]

                # garder la trace du minimum ansi le noeud suivant
                if val < min:
                    min = val
                    suiv = j
        # mise à jour des données du Noeud noeud
        self.couts[noeud][0] = min
        self.couts[noeud][1] = suiv

    # fonction principale
    def Dynamique(self):
        # initialiser les données du destination
        self.couts[-1][0] = 0
        self.couts[-1][1] = 11

        # pour chaque noeud à partir de la fin calculer le cout et remonter dans le graph jusqu'à le nœud source (S)
        for i in range(self.n-2, -1, -1):
            self.cout(i)

        # retourner le résultat
        return self.couts[0]


matriceAdj = [[0, 9, 7, 3, 2, 0, 0, 0, 0, 0, 0, 0],
              [0, 0, 0, 0, 0, 4, 2, 1, 0, 0, 0, 0],
              [0, 0, 0, 0, 0, 2, 7, 0, 0, 0, 0, 0],
              [0, 0, 0, 0, 0, 0, 0, 11, 0, 0, 0, 0],
              [0, 0, 0, 0, 0, 0, 11, 8, 0, 0, 0, 0],
              [0, 0, 0, 0, 0, 0, 0, 0, 6, 5, 0, 0],
              [0, 0, 0, 0, 0, 0, 0, 0, 4, 3, 0, 0],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 6, 0],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
              ]

couts = [[0, 0],
         [0, 0],
         [0, 0],
         [0, 0],
         [0, 0],
         [0, 0],
         [0, 0],
         [0, 0],
         [0, 0],
         [0, 0],
         [0, 0],
         [0, 0]
         ]

g = Graphe(matriceAdj, couts)
res = g.Dynamique()
suiv = res[1]
print("le plus court chemin de 1 à 12 est de longueur ", res[0])
print("1", end=" ")
while suiv != 11:
    print(" ----> ", end=" ")
    print(suiv+1, end=" ")
    suiv = g.couts[suiv][1]

print(" ----> ", end=" ")
print("12")
print(res)

le plus court chemin de 1 à 12 est de longueur  16
1  ---->  2  ---->  7  ---->  10  ---->  12