4.1 Définition des algorithmes gloutons.
Les algorithmes gloutons (Greedy Algorithms) — c'est une classe d'algorithmes qui construisent une solution en prenant des décisions localement optimales à chaque étape. Ces décisions sont basées sur l'état actuel et ne sont pas révisées plus tard.
Les algorithmes gloutons sont souvent utilisés pour résoudre les problèmes d'optimisation où l'objectif est de maximiser ou minimiser une certaine quantité.
Principes de base des algorithmes gloutons
- Choix glouton: À chaque étape, l'algorithme choisit la meilleure option locale qui, selon lui, mènera à une solution globalement optimale.
- Sous-structure optimale: Le problème doit avoir la propriété que les solutions localement optimales peuvent être combinées pour obtenir une solution globalement optimale.
- Monotonie: Une fois qu'une étape localement optimale est choisie, la solution ne doit pas être dégradée par les choix suivants.
Avantages et inconvénients des algorithmes gloutons
Avantages:
- Simplicité de mise en œuvre: Les algorithmes gloutons sont souvent simples à comprendre et à mettre en œuvre.
- Efficacité: Ils fonctionnent généralement plus rapidement que les algorithmes plus complexes, comme la programmation dynamique.
Inconvénients :
- Absence d'optimalité globale: Les algorithmes gloutons ne conduisent pas toujours à une solution globalement optimale.
- Pas adapté à tous les problèmes: Seuls certains problèmes peuvent être résolus par des algorithmes gloutons.
Il existe toute une classe de problèmes où la meilleure solution est obtenue par un algorithme glouton. Ça vaut le coup de les connaître.
4.2 Problème du rendu de monnaie.
Problème :
Nous avons des pièces de différentes valeurs. Il faut trouver le nombre minimal de pièces pour rendre une somme donnée.
Solution :
Il est toujours pris la pièce avec la plus grande valeur qui ne dépasse pas la somme restante.
Complexité temporelle : O(n), où n est le nombre de types de pièces.
Exemple de code en Python :
def min_coins(coins, amount):
coins.sort(reverse=True)
count = 0
for coin in coins:
while amount >= coin:
amount -= coin
count += 1
return count
4.3 Problème du sac à dos
Problème :
Nous avons des objets avec une valeur et un poids connus. Nous voulons les mettre dans un sac à dos de taille fixe pour obtenir une valeur maximale.
Dans cette variante du problème, les objets peuvent être fractionnés. Par exemple, nous voulons acheter différentes céréales, et on peut prendre aussi bien 1000 grammes que 512.
Solution :
Trier les objets par valeur spécifique (valeur/poids) et choisir les valeurs spécifiques les plus élevées jusqu'à ce que le sac à dos soit plein.
Complexité temporelle : O(n log n), où n est le nombre d'objets.
Exemple de code en Python :
class Item:
def __init__(self, value, weight):
self.value = value
self.weight = weight
self.ratio = value / weight
def fractional_knapsack(items, capacity):
items.sort(key=lambda x: x.ratio, reverse=True)
total_value = 0.0
for item in items:
if capacity >= item.weight:
total_value += item.value
capacity -= item.weight
else:
total_value += item.ratio * capacity
break
return total_value
4.4 Problème de couverture par segments
Problème :
Il y a des segments sur une ligne droite, définis par leurs extrémités (x1, x2), et un segment cible. Il faut trouver le nombre minimal de segments qui couvrent tous les points du segment cible.
Solution :
Trier les segments par l'extrémité droite et choisir le plus petit segment, couvrant le point actuel.
Complexité temporelle : O(n log n), où n est le nombre de segments.
Exemple de code en Python :
def min_segments(segments):
segments.sort(key=lambda x: x[1])
count = 0
end = -float('inf')
for seg in segments:
if seg[0] > end:
end = seg[1]
count += 1
return count
GO TO FULL VERSION