Algorithmes gloutons

Les algorithmes gloutons construisent une solution de manière incrémentale en effectuant de manière répétée le choix qui semble le meilleur à l'étape actuelle, et sont corrects précisément lorsque de tels choix localement optimaux mènent de manière démontrable à une solution globalement optimale.

Definition

Un algorithme glouton construit une solution à travers une séquence de choix, chacun étant choisi pour optimiser un critère local, sans jamais revenir sur des choix antérieurs ; il n'est correct que lorsque les choix localement optimaux produisent un résultat globalement optimal.

Scope

Ce sujet couvre le paradigme glouton : la propriété de choix glouton et la sous-structure optimale qui le justifient, les techniques de preuve standard (arguments d'échange et le cadre des matroïdes), et les algorithmes gloutons canoniques, notamment le codage de Huffman, les arbres couvrants minimaux (Kruskal et Prim), les plus courts chemins de Dijkstra et l'ordonnancement d'intervalles. Il aborde également les cas où les stratégies gloutonnes servent uniquement d'heuristiques d'approximation plutôt que de méthodes exactes.

Core questions

• Qu'est-ce que la propriété de choix glouton, et comment est-elle prouvée pour un problème donné ?
• Comment un argument d'échange démontre-t-il qu'un choix glouton est sûr ?
• Quels problèmes possèdent une structure de matroïde garantissant l'optimalité gloutonne ?
• Quand une méthode gloutonne n'est-elle qu'une approximation plutôt qu'un algorithme exact ?
• Comment l'approche gloutonne se compare-t-elle à la programmation dynamique pour le même problème ?

Key concepts

• propriété de choix glouton
• sous-structure optimale
• argument d'échange
• matroïdes
• codage de Huffman
• arbre couvrant minimal
• ordonnancement d'intervalles
• problème du sac à dos fractionnaire

Key theories

Propriété de choix glouton et arguments d'échange

Un problème admet une solution gloutonne lorsque une solution globalement optimale peut toujours être modifiée pour s'accorder avec le premier choix glouton sans perte d'optimalité ; les arguments d'échange (ou « le glouton garde l'avantage ») formalisent cela.

Matroïdes et optimalité gloutonne

Lorsque les solutions réalisables forment les ensembles indépendants d'un matroïde pondéré, l'algorithme glouton trouve toujours un ensemble indépendant de poids maximal ; cela unifie des résultats tels que l'optimalité de l'algorithme d'arbre couvrant minimal de Kruskal.

Clinical relevance

Les algorithmes gloutons sont à la base de systèmes largement utilisés : le codage de Huffman dans les formats de compression de données, les algorithmes d'arbres couvrants minimaux dans la conception de réseaux, l'algorithme de Dijkstra dans le routage et la navigation, et les heuristiques d'ordonnancement glouton et de couverture d'ensemble dans les systèmes d'exploitation et l'allocation de ressources.

History

Le raisonnement glouton apparaît dans des résultats classiques tels que les algorithmes d'arbres couvrants minimaux de Kruskal (1956) et de Prim (1957), les codes préfixes optimaux de Huffman (1952) et l'algorithme des plus courts chemins de Dijkstra (1959). L'explication basée sur la théorie des matroïdes concernant le succès des méthodes gloutonnes a été développée par Edmonds et d'autres dans les années 1960 et 1970.

Key figures

• David A. Huffman
• Joseph Kruskal
• Robert Prim
• Edsger W. Dijkstra

Seminal works

• dijkstra1959
• cormen2009

Frequently asked questions

Pourquoi l'approche gloutonne fonctionne-t-elle pour le problème du sac à dos fractionnaire mais pas pour le problème du sac à dos 0/1 ?

Dans le problème du sac à dos fractionnaire, les objets peuvent être divisés, donc prendre l'objet ayant la plus grande valeur par unité de poids en premier est toujours sûr et démontrablement optimal. Dans le problème du sac à dos 0/1, les objets sont indivisibles, le choix glouton peut empêcher une meilleure combinaison, et la programmation dynamique est nécessaire pour un optimum exact.

Comment prouver qu'un algorithme glouton est correct ?

Les deux techniques standard sont l'argument d'échange, qui transforme toute solution optimale en la solution gloutonne sans la détériorer, et l'argument « le glouton garde l'avantage », qui montre que la solution partielle gloutonne est au moins aussi bonne que toute autre à chaque étape. La théorie des matroïdes fournit une condition suffisante générale.