l'Algorithmie Avancée en Informatique: Exemples : problème du sac à dos, plus longue sous-séquence commune

Notions Fondamentales

1. Définition

La programmation dynamique est une méthode pour résoudre des problèmes de manière récursive, mais en stockant les résultats intermédiaires afin d'éviter de recalculer les mêmes sous-problèmes plusieurs fois. Cela se fait généralement en utilisant un tableau ou une structure de données similaire.

2. Propriétés

Décomposition : Le problème est décomposé en sous-problèmes plus simples.
Optimalité : La solution globale est construite à partir des solutions optimales des sous-problèmes.
Mémorisation : Les résultats des sous-problèmes sont mémorisés pour éviter des calculs redondants.

Exemple 2 : Problème du Sac à Dos

Le problème du sac à dos consiste à sélectionner des objets avec des poids et des valeurs donnés pour maximiser la valeur totale tout en respectant une contrainte de poids maximale.

Code :

// Fonction pour résoudre le problème du sac à dos en utilisant la programmation dynamique
function knapSack(W, weights, values, n) {
    let K = Array(n + 1).fill().map(() => Array(W + 1).fill(0)); // Tableau pour mémoriser les résultats

    for (let i = 0; i <= n; i++) {
        for (let w = 0; w <= W; w++) {
            if (i === 0 || w === 0) {
                K[i][w] = 0; // Initialisation des cas de base
            } else if (weights[i - 1] <= w) {
                // Choisir l'objet i ou pas
                K[i][w] = Math.max(values[i - 1] + K[i - 1][w - weights[i - 1]], K[i - 1][w]);
            } else {
                K[i][w] = K[i - 1][w]; // Ne pas choisir l'objet i
            }
        }
    }
    return K[n][W]; // Valeur maximale possible
}

// Données d'entrée
let values = [60, 100, 120];
let weights = [10, 20, 30];
let W = 50;
let n = values.length;

// Exemple d'utilisation
console.log(knapSack(W, weights, values, n)); // Output: 220

Interface de Test en HTML et JavaScript

HTML

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Programmation Dynamique - Interface de Test</title>
    <style>
        body {
            font-family: Arial, sans-serif;
        }
        .container {
            margin: 20px;
        }
        .input-group {
            margin-bottom: 10px;
        }
        .input-group label {
            margin-right: 10px;
        }
        .result {
            margin-top: 20px;
        }
    </style>
</head>
<body>
    <div class="container">
        <h1>Programmation Dynamique - Interface de Test</h1>
        <div class="input-group">
            <label for="fib-input">Nombre de Fibonacci (n):</label>
            <input type="number" id="fib-input" value="10">
            <button onclick="calculateFibonacci()">Calculer</button>
        </div>
        <div class="input-group">
            <label for="knap-input-values">Valeurs (séparées par des virgules):</label>
            <input type="text" id="knap-input-values" value="60,100,120">
        </div>
        <div class="input-group">
            <label for="knap-input-weights">Poids (séparés par des virgules):</label>
            <input type="text" id="knap-input-weights" value="10,20,30">
        </div>
        <div class="input-group">
            <label for="knap-input-capacity">Capacité du sac (W):</label>
            <input type="number" id="knap-input-capacity" value="50">
            <button onclick="calculateKnapsack()">Calculer</button>
        </div>
        <div class="result" id="result"></div>
    </div>
    <script src="dynamic_programming.js"></script>
</body>
</html>

JavaScript (dynamic_programming.js)


// Fonction pour résoudre le problème du sac à dos en utilisant la programmation dynamique
function knapSack(W, weights, values, n) {
    let K = Array(n + 1).fill().map(() => Array(W + 1).fill(0)); // Tableau pour mémoriser les résultats

    for (let i = 0; i <= n; i++) {
        for (let w = 0; w <= W; w++) {
            if (i === 0 || w === 0) {
                K[i][w] = 0; // Initialisation des cas de base
            } else if (weights[i - 1] <= w) {
                // Choisir l'objet i ou pas
                K[i][w] = Math.max(values[i - 1] + K[i - 1][w - weights[i - 1]], K[i - 1][w]);
            } else {
                K[i][w] = K[i - 1][w]; // Ne pas choisir l'objet i
            }
        }
    }
    return K[n][W]; // Valeur maximale possible
}

// Fonction pour afficher le résultat de Fibonacci
function calculateFibonacci() {
    const n = parseInt(document.getElementById('fib-input').value);
    const result = fibonacciDP(n); // Utilisation de l'approche bottom-up
    document.getElementById('result').innerHTML = `Fibonacci(${n}) = ${result}`;
}

// Fonction pour afficher le résultat du sac à dos
function calculateKnapsack() {
    const values = document.getElementById('knap-input-values').value.split(',').map(Number);
    const weights = document.getElementById('knap-input-weights').value.split(',').map(Number);
    const W = parseInt(document.getElementById('knap-input-capacity').value);
    const n = values.length;
    const result = knapSack(W, weights, values, n);
    document.getElementById('result').innerHTML = `Valeur maximale possible = ${result}`;
}

Cas Réels d'Utilisation

Optimisation des Stocks :
- Utilisation de la programmation dynamique pour déterminer la quantité optimale de produits à stocker en fonction des prévisions de ventes et des coûts de stockage.
Planification de Projets :
- Utilisation de la programmation dynamique pour optimiser l'allocation des ressources et des tâches afin de minimiser le temps et les coûts de réalisation des projets.
Séquençage ADN :
- Utilisation de la programmation dynamique pour comparer des séquences d'ADN et identifier les similarités et les différences, ce qui est essentiel pour la recherche en génétique et en biologie moléculaire.
Jeux Vidéo :
- Utilisation de la programmation dynamique pour implémenter des IA de jeu optimales, par exemple pour déterminer les chemins les plus courts ou pour optimiser les stratégies de jeu.

Conclusion

La programmation dynamique est une technique puissante pour résoudre des problèmes complexes d'optimisation en les décomposant en sous-problèmes plus simples et en mémorisant les résultats intermédiaires. Les cas réels d'utilisation montrent l'applicabilité de la programmation dynamique dans divers domaines de l'informatique et au-delà.

Modifié le: lundi 3 juin 2024, 08:16