Algorithme Glouton (Greedy Algorithm)

Ce document présente les concepts fondamentaux des algorithmes gloutons, destinés aux étudiants en algorithmique avancée. Il explique le principe général, illustre des problèmes classiques et propose une méthode de résolution basée sur ce paradigme. Des exemples concrets sont fournis pour faciliter la compréhension et la mise en œuvre.

Principe de l’Algorithme Glouton

Un algorithme glouton construit une solution étape par étape en faisant à chaque fois le choix qui semble optimal localement, sans revenir sur les décisions prises. Ce processus peut parfois conduire à la solution optimale globale, on parle alors d’algorithmes gloutons exacts. Dans d’autres cas, il s’agit d’heuristiques gloutonnes qui fournissent une solution approchée.

Exemple classique : Rendre la monnaie

On dispose d’un ensemble infini de pièces de monnaie de valeurs {a0, a1, ..., an−1} avec 1 = a0 < a1 < ... < an−1. Le but est, pour une somme entière c donnée, de trouver une combinaison de pièces qui rende cette somme avec un nombre minimal de pièces.

Le principe glouton consiste à choisir à chaque étape la pièce de plus grande valeur possible qui ne dépasse pas la somme restante à rendre.

Exemple

Supposons les pièces {1, 5, 10, 25} et une somme à rendre c = 37.

• Choisir la pièce 25 (plus grande valeur ≤ 37), reste 12
• Choisir la pièce 10 (plus grande valeur ≤ 12), reste 2
• Choisir la pièce 1 (plus grande valeur ≤ 2), reste 1
• Choisir la pièce 1 (plus grande valeur ≤ 1), reste 0

Nombre total de pièces : 4 (25 + 10 + 1 + 1).

Application : Gestion des films dans un cinéma

Un cinéma possède s salles et propose chaque semaine une liste de films à diffuser. Chaque film est caractérisé par une date de début (di), une date de fin (fi) et le numéro de la salle (numSi) où il est projeté. Un amateur souhaite voir le maximum de films dans une journée, sachant qu’il peut voir un même film plusieurs fois.

Modélisation du problème

• A = {a1, a2, ..., an} : ensemble des films diffusés pendant la journée
• Chaque film ai est défini par di (date de début), fi (date de fin) et numSi (numéro de salle)
• Deux films ai et aj sont compatibles si leurs intervalles ne se chevauchent pas, c’est-à-dire dj ≥ fi ou di ≥ fj
• Objectif : sélectionner le plus grand nombre de films compatibles à voir

Algorithme glouton pour la sélection des films

L’idée est de trier les films par date de fin croissante, puis de sélectionner successivement les films compatibles avec ceux déjà choisis.

public Film choixFilm(Film[] A) {
    Film[] M; // M contient les films sélectionnés
    trier(A); // trier selon la date de fin fi croissante
    M[0] = A[0];
    int nbfilm = 1;
    int i = 1;
    while (i < A.length) {
        if (A[i].d >= M[nbfilm - 1].f) {
            M[nbfilm] = A[i];
            nbfilm++;
        }
        i++;
    }
    return M;
}

Explication de l’algorithme

• On commence par trier la liste des films par date de fin croissante.
• On sélectionne le premier film (celui qui finit le plus tôt).
• Pour chaque film suivant, on vérifie s’il commence après la fin du dernier film sélectionné.
• Si oui, on l’ajoute à la sélection.
• On continue jusqu’à avoir parcouru tous les films.

Cadre général d’un algorithme glouton

Pour concevoir un algorithme glouton efficace, il faut :

• Définir un critère objectif qui guide la construction de la solution.
• Choisir un critère de sélection qui paraît optimal à chaque étape (souvent simple à identifier).
• Implémenter l’algorithme de manière efficace, généralement facile et rapide.

Glossaire des termes clés

• Algorithme glouton : méthode algorithmique construisant une solution étape par étape en faisant à chaque fois le choix localement optimal.
• Heuristique gloutonne : algorithme glouton qui ne garantit pas la solution optimale globale mais fournit une solution approchée.
• Critère objectif : mesure ou propriété que l’on cherche à optimiser dans un problème.
• Critère de sélection : règle utilisée à chaque étape pour choisir l’élément à ajouter à la solution.
• Films compatibles : deux films dont les intervalles de diffusion ne se chevauchent pas.
• Tri par date de fin : opération consistant à ordonner les films selon leur date de fin croissante.

Points clés à retenir

• Un algorithme glouton fait des choix locaux optimaux sans revenir en arrière.
• Il peut être exact ou heuristique selon le problème.
• Le problème de rendre la monnaie illustre bien le principe glouton.
• La sélection maximale de films compatibles est un autre exemple classique.
• Le tri préalable des éléments est souvent une étape cruciale dans les algorithmes gloutons.
• La simplicité et l’efficacité sont des avantages majeurs des algorithmes gloutons.