Algorithmes gloutons
Qu'est-ce qui rend un algorithme glouton ?
Un algorithme glouton construit une solution étape par étape, en choisissant toujours l'option qui semble la meilleure sur le moment - sans revenir sur ses choix passés. Pas de retour sur trace, pas d'anticipation.
Il fonctionne quand deux propriétés sont réunies :
- Propriété de choix glouton - un choix localement optimal mène à une solution globalement optimale.
- Sous-structure optimale - le problème restant après chaque choix est une instance plus petite du même problème.
Sélection d'activités - L'exemple classique
Étant donné un ensemble d'activités avec des heures de début et de fin, sélectionnez le nombre maximum d'activités non chevauchantes.
Stratégie gloutonne : trier par heure de fin, toujours choisir l'activité qui se termine le plus tôt.
def max_activities(intervals):
intervals.sort(key=lambda x: x[1])
count, end = 0, 0
for s, e in intervals:
if s >= end:
count += 1
end = e
return count
Pourquoi ça marche ? Choisir l'activité qui finit le plus tôt laisse le plus de place pour les activités suivantes.
Codage de Huffman - Le concept
On construit un code binaire préfixe optimal en fusionnant répétitivement les deux symboles de plus basse fréquence. C'est glouton : à chaque étape, on fusionne la paire la moins coûteuse. Le résultat est un arbre où les symboles fréquents reçoivent des codes courts.
Jump Game
Étant donné un tableau où nums[i] est la longueur maximale du saut depuis l'index i, déterminez si vous pouvez atteindre le dernier index.
Approche gloutonne : suivre l'index le plus loin atteignable. Parcourir de gauche à droite - si on reste bloqué, retourner false.
def can_jump(nums):
farthest = 0
for i, jump in enumerate(nums):
if i > farthest:
return False
farthest = max(farthest, i + jump)
return True
Discussion
Se connecter pour rejoindre la discussion