Application DP aux problèmes réels

7.1 Optimisation des algorithmes dynamiques.

L'optimisation des algorithmes dynamiques vise à améliorer leur efficacité en termes de temps et d'espace. Il existe plusieurs approches pour optimiser, notamment l'utilisation de la mémorisation, la réduction de la mémoire utilisée et l'optimisation de la récursivité.

1. Mémorisation :

La mémorisation est une technique où les résultats des calculs sont sauvegardés pour éviter les recalculs de la même sous-tâche.

Exemple :

Dans le problème du change de monnaie, si on utilise une approche récursive, on peut sauvegarder les résultats pour les sommes déjà calculées afin d'éviter les recalculs.

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]
        
        

2. Solution tabulaire (Bottom-Up):

La solution tabulaire (bottom-up) construit une table de solutions pour toutes les sous-tâches possibles du cas de base jusqu'à la tâche cible. Cela permet d'éviter les frais généraux des appels récursifs.

Exemple :

Dans le problème du sac à dos, on construit une table de quantités minimales de pièces pour chaque somme de 0 à S.

def fibonacci(n):
    dp = [0] * (n + 1)
    dp[1] = dp[2] = 1
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
        
        

3. Réduction de la mémoire utilisée :

Dans certains problèmes, il est possible d'optimiser l'utilisation de la mémoire en réduisant la taille de la table ou du tableau utilisé pour stocker les résultats intermédiaires.

Exemple :

Dans le problème du sac à dos, on peut utiliser un tableau unidimensionnel au lieu d'une table bidimensionnelle si on ne garde que la ligne actuelle et la précédente.

def knapsack_optimized(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]
        
        

4. Récursivité terminale :

La récursivité terminale est un appel récursif qui est exécuté à la fin de la fonction. Cela permet au compilateur ou à l'interpréteur d'optimiser la pile d'appels.

Exemple :

Dans le problème du calcul des nombres de Fibonacci, on peut utiliser la récursivité terminale avec un accumulateur de résultats.

7.2 Application du Dynamic Programming dans les problèmes réels.

Le Dynamic Programming trouve une large application dans divers domaines, y compris les sciences informatiques, l'économie, la bioinformatique et la recherche opérationnelle. Voici quelques exemples de son utilisation dans des problèmes réels :

1. Optimisation des itinéraires et logistique :

Dans les problèmes de logistique et de systèmes de transport, le Dynamic Programming est utilisé pour trouver les itinéraires optimaux et minimiser les coûts.

Exemple :

Le problème du voyageur de commerce (Travelling Salesman Problem, TSP) — trouver le chemin le plus court passant par toutes les villes.

def tsp(graph, start):
    n = len(graph)
    dp = [[None] * (1 << n) for _ in range(n)]

    def visit(city, visited):
        if visited == (1 << n) - 1:
            return graph[city][start]
        if dp[city][visited] is not None:
            return dp[city][visited]
        result = float('inf')
        for next_city in range(n):
            if visited & (1 << next_city) == 0:
                result = min(result, graph[city][next_city] + visit(next_city, visited | (1 << next_city)))
        dp[city][visited] = result
        return result

    return visit(start, 1 << start)

2. Alignement des séquences en bioinformatique :

En bioinformatique, le Dynamic Programming est utilisé pour aligner les séquences d'ADN, d'ARN et de protéines.

Exemple :

L'algorithme de Needleman-Wunsch pour l'alignement global des séquences et l'algorithme de Smith-Waterman pour l'alignement local.

def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]
        

3. Calculs financiers et planification économique :

Le Dynamic Programming est appliqué pour optimiser les portefeuilles d'investissement, gérer les risques et planifier la production.

Exemple :

Le problème du change de monnaie et le problème du sac à dos sont utilisés pour la gestion des actifs et la répartition optimale des ressources.

4. Gestion des stocks et production :

Dans la production et la gestion des stocks, le Dynamic Programming aide à optimiser les processus et minimiser les coûts.

Exemple :

Le modèle de gestion des stocks (Inventory Management Model) pour minimiser les coûts de stockage et de commande de produits.

5. Apprentissage automatique et intelligence artificielle :

Dans l'apprentissage automatique, le Dynamic Programming est utilisé pour optimiser les algorithmes et trouver des optima globaux.

Exemple :

Les algorithmes d'apprentissage basés sur le Dynamic Programming, comme la méthode de rétropropagation dans les réseaux neuronaux.