Chapitre 4 : Programmation Gloutonne

4.1 Introduction

La programmation gloutonne est une stratégie de résolution de problèmes d'optimisation combinatoire où l'on fait des choix localement optimaux à chaque étape, sans revenir en arrière. Contrairement à la programmation dynamique, qui résout des sous-problèmes pour construire une solution globale, la programmation gloutonne prend des décisions immédiates en espérant qu'elles mènent à une solution globale optimale.

Avantages :

  • Complexité souvent polynomiale (plus rapide que les méthodes exactes pour les problèmes NP-difficiles).
  • Simple à implémenter.
Inconvénients :
  • Ne garantit pas toujours une solution optimale.
  • Nécessite une preuve pour vérifier l'optimalité.

Exemple : Dans un graphe pondéré, pour trouver un chemin de poids minimal, un algorithme glouton pourrait choisir à chaque étape l'arête de plus faible poids.

4.2 Arbre couvrant de poids minimal (ACPM)

Un arbre couvrant de poids minimal (ACPM) est un sous-ensemble d'arêtes d'un graphe connexe qui :

  • Connecte tous les sommets.
  • Est acyclique (sans cycle).
  • A un poids total minimal.

Propriété clé pour les algorithmes gloutons

Propriété : Pour toute coupe d'un graphe pondéré, l'arête de poids minimal qui traverse cette coupe fait partie de l'ACPM.
Cela permet de construire l'ACPM en ajoutant à chaque étape l'arête de poids minimal qui ne forme pas de cycle.

Algorithmes pour l'ACPM

  1. Algorithme de Borůvka :
    • Fusionne des composantes connexes en ajoutant l'arête de poids minimal entre elles.
    • Complexité : O(m log n) (avec m = nombre d'arêtes, n = nombre de sommets).
  2. Algorithme de Kruskal :
    • Trie toutes les arêtes par poids croissant.
    • Ajoute les arêtes une par une en évitant les cycles (utilise une structure Union-Find).
    • Complexité : O(m log n).
    • Adapté aux graphes denses (beaucoup d'arêtes).
  3. Algorithme de Prim :
    • Part d'un sommet et ajoute à chaque étape l'arête de poids minimal qui connecte un sommet déjà inclus à un sommet non inclus.
    • Complexité : O(m + n log n) avec une file de priorité.
    • Adapté aux graphes peu denses (peu d'arêtes).
4.3 Coloration de graphes

La coloration de graphes consiste à attribuer une couleur à chaque sommet de sorte que deux sommets adjacents n'aient pas la même couleur. L'objectif est de minimiser le nombre de couleurs utilisées.

Algorithme glouton pour la coloration

  1. Trier les sommets par degré décroissant (nombre de voisins).
  2. Pour chaque sommet, attribuer la première couleur disponible qui n'est pas utilisée par ses voisins.

Problème : Cet algorithme ne garantit pas une solution optimale, car le nombre de couleurs dépend de l'ordre de traitement des sommets.
Complexité : O(n^2) (avec n = nombre de sommets).

Exemple : Le graphe de Petersen (figure 4.3) peut être colorié avec 3 couleurs, mais l'algorithme glouton peut en utiliser 4 selon l'ordre des sommets.

4.4 Problème du choix d'activités

Le problème du choix d'activités consiste à sélectionner un ensemble maximal d'activités compatibles (non chevauchantes) parmi un ensemble donné. Chaque activité a une date de début et de fin.

Critères gloutons

Plusieurs critères peuvent être utilisés, mais seul l'un d'eux garantit une solution optimale :

  1. Critère 1 : Durée la plus courte → Non optimal (peut laisser des intervalles inutilisés).
  2. Critère 2 : Date de début la plus précoce → Non optimal.
  3. Critère 3 : Date de fin la plus précoce → Optimal.
    • L'algorithme trie les activités par date de fin croissante.
    • Il sélectionne la première activité, puis la prochaine activité compatible (qui commence après la fin de la précédente).
    • Complexité : O(n log n) (à cause du tri initial).

Preuve d'optimalité

Pour prouver que le critère "date de fin la plus précoce" est optimal, on montre que :

  1. Il existe une solution optimale qui inclut l'activité qui se termine le plus tôt.
  2. Le sous-problème restant (activités commençant après la fin de cette activité) peut être résolu de manière optimale.

4.5 Éléments de stratégie gloutonne

Pour concevoir un algorithme glouton optimal, il faut :

  1. Trouver une sous-structure optimale : Le problème doit pouvoir être décomposé en sous-problèmes dont les solutions optimales contribuent à la solution globale.
  2. Prouver que le choix glouton est optimal : Montrer qu'il existe toujours une solution optimale qui inclut le choix glouton.
  3. Prouver que le sous-problème restant est optimal : Montrer que la solution optimale du sous-problème (après le choix glouton) conduit à une solution optimale globale.

Différence entre programmation gloutonne et dynamique

Critère Programmation Gloutonne Programmation Dynamique
Approche Descendante (choix local → solution globale) Ascendante (sous-problèmes → problème global)
Complexité Souvent polynomiale Souvent exponentielle ou polynomiale
Optimalité Pas toujours garantie Toujours garantie (si bien conçue)
Exemple Algorithme de Kruskal Algorithme de Fibonacci
4.6 Synthèse

À la fin de ce chapitre, vous devriez être capable de :

  • Comprendre les principes de la programmation gloutonne et ses limites.
  • Appliquer des algorithmes gloutons pour résoudre des problèmes comme :
    • Recherche d'un arbre couvrant de poids minimal (Borůvka, Kruskal, Prim).
    • Coloration de graphes (avec un nombre minimal de couleurs).
    • Problème du choix d'activités (avec le critère optimal).
  • Concevoir un algorithme glouton en suivant les étapes de preuve d'optimalité.
  • Différencier la programmation gloutonne de la programmation dynamique.

Remarque : La programmation gloutonne ne fonctionne pas pour tous les problèmes (ex : problème du voyageur de commerce, coloration optimale de graphes). Dans ces cas, on utilise des heuristiques ou des algorithmes d'approximation.

QCM : Testez vos connaissances (30 questions)

Répondez à toutes les questions pour valider votre maîtrise du chapitre.