Les Algorithmes Gloutons

Introduction

Les algorithmes gloutons (ou gourmands) sont une approche algorithmique qui fait des choix successifs pour arriver à une solution optimale. À chaque étape, un algorithme glouton choisit l'option qui semble la meilleure à ce moment précis, sans se préoccuper des conséquences futures. Cette approche est souvent utilisée pour résoudre des problèmes d'optimisation.

Notions Fondamentales

1. Définition

Un algorithme glouton prend des décisions basées sur l'information disponible à chaque étape pour trouver une solution globale. Il est généralement simple et rapide, mais ne garantit pas toujours une solution optimale pour tous les problèmes.

2. Propriétés

• Localement Optimal : Chaque étape choisit la meilleure option disponible.
• Globalement Optimal : Si la solution locale conduit à la solution optimale globale (ce qui n'est pas toujours garanti).

3. Applications

• Problème du Sac à Dos Fractionnaire : Sélection des objets pour maximiser la valeur totale tout en respectant une contrainte de poids.
• Problème de la Monnaie : Donner la monnaie avec le minimum de pièces possible.
• Problème de l'Arbre de Recouvrement Minimal : Trouver un arbre de recouvrement minimal dans un graphe.

Exemple 1 : Problème du Sac à Dos Fractionnaire

Nous allons implémenter un algorithme glouton pour résoudre le problème du sac à dos fractionnaire. Ce problème consiste à maximiser la valeur totale des objets placés dans un sac à dos de capacité limitée, en permettant de prendre des fractions d'objets.

Implémentation en JavaScript

// Classe représentant un objet avec une valeur et un poids
class Item {
    constructor(value, weight) {
        this.value = value;
        this.weight = weight;
    }
}

// Fonction pour résoudre le problème du sac à dos fractionnaire
function knapsack(items, capacity) {
    // Tri des objets par valeur unitaire décroissante (valeur/poids)
    items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));

    let totalValue = 0; // Valeur totale maximale pouvant être mise dans le sac
    for (let item of items) {
        if (capacity > 0 && item.weight <= capacity) {
            capacity -= item.weight; // Réduit la capacité du sac
            totalValue += item.value; // Ajoute la valeur de l'objet
        } else if (capacity > 0) {
            totalValue += item.value * (capacity / item.weight); // Prend une fraction de l'objet
            break;
        }
    }
    return totalValue; // Retourne la valeur totale maximale
}

// Exemple d'utilisation
let items = [
    new Item(60, 10),
    new Item(100, 20),
    new Item(120, 30)
];
let capacity = 50;

console.log(knapsack(items, capacity)); // Output: 240

Explication du Code

Classe Item

• Objectif : La classe Item représente un objet avec deux propriétés : sa valeur et son poids.
• Constructeur : Le constructeur initialise un nouvel objet Item avec les valeurs spécifiées pour value (valeur de l'objet) et weight (poids de l'objet).

Fonction knapsack

• Objectif : La fonction knapsack résout le problème du sac à dos fractionnaire, où l'objectif est de maximiser la valeur totale des objets placés dans un sac à dos de capacité limitée.
• Paramètres :
  • items : Un tableau d'objets de type Item.
  • capacity : La capacité maximale du sac à dos.
• Étapes de l'algorithme :
  • Tri : Les objets sont triés par valeur unitaire décroissante (valeur/poids). Cela signifie que les objets avec la plus grande valeur par unité de poids seront considérés en premier.
  • Initialisation : Une variable totalValue est initialisée à 0 pour garder la trace de la valeur totale des objets ajoutés au sac.
  • Boucle sur les objets :
    • Pour chaque objet dans le tableau trié :
      • Si la capacité restante du sac est suffisante pour contenir l'objet en entier, l'objet est ajouté au sac :
        • La capacité du sac est réduite du poids de l'objet.
        • La valeur de l'objet est ajoutée à totalValue.
      • Si la capacité restante du sac ne peut contenir qu'une fraction de l'objet, une fraction proportionnelle de l'objet est ajoutée au sac :
        • La valeur ajoutée est proportionnelle à la fraction de l'objet ajoutée.
        • La boucle se termine car le sac est maintenant plein.
  • Retour : La fonction retourne la valeur totale maximale des objets qui peuvent être placés dans le sac à dos.

Exemple d'utilisation

• Création des objets : Trois objets de type Item sont créés avec des valeurs et des poids spécifiques :
  • Un objet avec une valeur de 60 et un poids de 10.
  • Un objet avec une valeur de 100 et un poids de 20.
  • Un objet avec une valeur de 120 et un poids de 30.
• Capacité du sac à dos : La capacité maximale du sac à dos est définie à 50.
• Appel de la fonction knapsack : La fonction est appelée avec le tableau des objets et la capacité du sac à dos. Le résultat est la valeur maximale des objets qui peuvent être placés dans le sac, soit 240 dans cet exemple.

Résumé

Ce code implémente un algorithme glouton pour résoudre le problème du sac à dos fractionnaire. En triant les objets par valeur unitaire décroissante et en ajoutant autant d'objets que possible au sac à dos jusqu'à ce qu'il soit plein, l'algorithme trouve une solution qui maximise la valeur totale des objets dans le sac.

Exemple 2 : Problème de la Monnaie

Nous allons implémenter un algorithme glouton pour résoudre le problème de la monnaie, qui consiste à donner un montant avec le minimum de pièces possible.

Implémentation en JavaScript

// Fonction pour résoudre le problème de la monnaie
function minCoins(coins, amount) {
    coins.sort((a, b) => b - a); // Tri des pièces par ordre décroissant

    let count = 0; // Nombre de pièces utilisées
    for (let coin of coins) {
        while (amount >= coin) {
            amount -= coin; // Réduit le montant par la valeur de la pièce
            count++; // Incrémente le nombre de pièces utilisées
        }
    }
    return count; // Retourne le nombre de pièces utilisées
}

// Exemple d'utilisation
let coins = [1, 5, 10, 25];
let amount = 63;

console.log(minCoins(coins, amount)); // Output: 6

Explication du Code

Fonction minCoins

• Objectif : La fonction minCoins résout le problème de la monnaie, qui consiste à donner un montant avec le minimum de pièces possible.

• Paramètres :

  • coins : Un tableau contenant les différentes valeurs des pièces disponibles.
  • amount : Le montant total que l'on souhaite donner.

• Étapes de l'algorithme :

  • Tri des pièces : Les pièces sont triées par ordre décroissant de valeur. Cela permet de commencer par utiliser les pièces de plus grande valeur, ce qui aide à minimiser le nombre total de pièces utilisées.
    coins.sort((a, b) => b - a);
  • Initialisation du compteur : Une variable count est initialisée à 0 pour garder la trace du nombre total de pièces utilisées.
    let count = 0;
  • Boucle sur les pièces :
    • Pour chaque pièce dans le tableau trié :
      • Boucle interne : Tant que le montant restant (amount) est supérieur ou égal à la valeur de la pièce actuelle (coin), on effectue les opérations suivantes :
        • Le montant est réduit de la valeur de la pièce.
        • Le compteur de pièces utilisées est incrémenté.
        for (let coin of coins) { while (amount >= coin) { amount -= coin; count++; } }
  • Retour : La fonction retourne le nombre total de pièces utilisées pour donner le montant spécifié.
    return count;

Exemple d'utilisation

• Définition des pièces : Un tableau de pièces est défini avec les valeurs 1, 5, 10 et 25.
  let coins = [1, 5, 10, 25];
• Définition du montant : Le montant total à donner est défini à 63.
  let amount = 63;
• Appel de la fonction minCoins : La fonction est appelée avec le tableau de pièces et le montant total. Le résultat est le nombre minimal de pièces nécessaires pour atteindre le montant, soit 6 dans cet exemple.
  console.log(minCoins(coins, amount)); // Output: 6

Résumé

Ce code implémente un algorithme glouton pour résoudre le problème de la monnaie. En triant les pièces par ordre décroissant et en utilisant autant de pièces de grande valeur que possible avant de passer aux pièces de valeur inférieure, l'algorithme minimise le nombre total de pièces nécessaires pour donner un montant spécifié.

Conclusion

Les algorithmes gloutons sont une approche simple et efficace pour résoudre certains problèmes d'optimisation. Bien qu'ils ne garantissent pas toujours une solution optimale, ils sont souvent suffisants pour de nombreux problèmes pratiques. Les exemples du sac à dos fractionnaire et du problème de la monnaie montrent comment cette approche peut être appliquée pour trouver des solutions rapides et efficaces.