Publié · en amélioration
Algorithm
Les algorithmes gloutons font à chaque étape le meilleur choix local, sans retour : ordonnancement d'intervalles, codage de Huffman, sac à dos fractionnaire.
Un algorithme glouton construit sa solution par une suite de décisions : à chaque étape, il prend le candidat qui semble le meilleur selon une règle fixe et ne remet jamais ce choix en cause. La plupart trient les candidats ou les placent dans une file de priorité, puis les acceptent un par un ; le code est donc court et le temps d'exécution est généralement en O(n log n), dominé par le tri ou les opérations sur le tas.
Quand elle fonctionne, l'approche gloutonne est la solution la plus rapide et la plus simple, mais elle ne fonctionne pas toujours. Pour garantir l'optimum, il faut la propriété du choix glouton et une sous-structure optimale, ce que l'on démontre le plus souvent par un argument d'échange. Un seul contre-exemple, comme rendre 6 avec des pièces de 1, 3 et 4, suffit à montrer qu'il faut passer à la programmation dynamique. Le principe glouton est aussi au cœur d'algorithmes très utilisés : codage de Huffman, plus courts chemins de Dijkstra, arbres couvrants de poids minimal.
Commencez par l'ordonnancement d'intervalles (sélection d'activités) et expliquez, avec un argument d'échange, pourquoi choisir la réunion qui se termine en premier est correct. Implémentez ensuite le codage de Huffman, le sac à dos fractionnaire et l'attribution de salles avec un tas, et prenez l'habitude de comparer vos résultats gloutons à une recherche exhaustive sur de petites entrées : c'est le moyen le plus rapide de repérer une règle fausse en entretien technique.
Il doit exister une solution optimale contenant le premier choix glouton ; c'est la condition clé pour que l'algorithme soit correct.
On montre que toute solution optimale peut être transformée, élément par élément, en la solution gloutonne sans se dégrader.
Les candidats sont classés par heure de fin, valeur par poids ou fréquence, ou extraits d'un tas, d'où un coût habituel en O(n log n).
Pour un système de pièces quelconque ou le sac à dos 0/1, la règle gloutonne se trompe et la programmation dynamique prend le relais.
Le programme choisit le plus grand ensemble de réunions qui ne se chevauchent pas. Il trie les réunions par heure de fin et n'accepte une réunion que si elle commence après la fin de la dernière retenue. Le tri coûte O(n log n) et le parcours O(n) ; dans l'exemple, 4 des 11 réunions sont retenues.
greedy.py
def select_intervals(intervals):
"""Return a maximum set of non-overlapping half-open intervals [start, end)."""
chosen = []
last_end = float("-inf")
for start, end in sorted(intervals, key=lambda iv: iv[1]): # earliest end first
if start >= last_end:
chosen.append((start, end))
last_end = end
return chosen
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(select_intervals(meetings)) # [(1, 4), (5, 7), (8, 11), (12, 16)]
python greedy.pySix chapitres pour aller de l'installation aux notions essentielles de Algorithmes gloutons.
Posez vos questions, partagez votre expérience et échangez vos avis sur Algorithmes gloutons.
Aucune discussion pour l'instant. Lancez la première.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.