Algorithmes gloutons: cours introductoire

• Les algorithmes gloutons sont une méthode de résolution de problèmes algorithmiques basée sur le choix localement optimal à chaque étape, dans l'espoir d'une solution globalement optimale.

Principe général

• L'algorithme glouton consiste à faire le choix qui semble le meilleur sur le moment, sans considérer les conséquences futures.
• Le but est d'obtenir une solution globalement optimale en faisant une série de choix optimaux localement.
• Exemple : Pour rendre 17€ avec le moins de pièces, on choisit successivement les pièces de 10€, 5€, puis 2€.

Avantages et inconvénients

• Simples à concevoir et à implémenter.
• Généralement efficaces en termes de temps de calcul.
• Ne garantissent pas toujours la solution optimale globale.
• Peuvent ne pas trouver de solution dans certains cas.
• Exemple : Avec des pièces de 1€, 3€ et 4€, rendre 6€ avec un algorithme glouton donne 4€ + 1€ + 1€ (3 pièces), alors que l'optimal est 3€ + 3€ (2 pièces)

Quand utiliser un algorithme glouton ?

• Adaptés aux problèmes avec optimalité locale et sous-structure optimale.
• Optimalité locale : un choix localement optimal contribue à une solution globalement optimale.
• Sous-structure optimale : la solution optimale d'un problème contient les solutions optimales des sous-problèmes.
• Il est souvent difficile de prouver formellement ces propriétés.
• Il est important de tester l'algorithme sur un ensemble varié de données pour assurer des résultats satisfaisants.

Exemples d'applications

• Rendu de monnaie (optimal si le système monétaire est canonique).
• Couverture d'ensemble (trouver le plus petit nombre de sous-ensembles recouvrant l'ensemble initial).
• Algorithme de Dijkstra (calcul des plus courts chemins dans un graphe pondéré).
• Arbre couvrant minimal (algorithmes de Kruskal ou Prim).
• Compression de données (algorithme de Huffman).

Exercices

• Ordonnancement de tâches : minimiser le retard maximal en ordonnançant des tâches avec durées et échéances.
• Sac à dos fractionnaire : maximiser la valeur totale transportée en fractionnant des objets avec poids et valeurs, dans un sac à dos de capacité limitée.