Algorithme glouton
Période historique : XXe siècle
La stratégie myope : choisir à chaque étape le meilleur gain local immédiat dans l'espoir d'atteindre l'optimum global.
Contenu & Formulation mathématique
Genèse & Portée historique
Paradigme algorithmique de résolution de problèmes d'optimisation consistant à faire le choix qui paraît le plus avantageux à l'instant présent sans jamais remettre en cause les décisions antérieures. Il est optimal pour certains problèmes (Kruskal, Dijkstra, Huffman).
Bien que l'intuition gloutonne échoue sur certains problèmes célèbres (comme le problème du voyageur de commerce ou le rendu de monnaie avec des pièces arbitraires), la théorie des matroïdes caractérise exactement les structures où la gloutonnerie est parfaite.
Filiations & Relations conceptuelles (0)
Cette notice constitue un axiome autonome sans relations directes enregistrées dans le recueil.
Objet de collection MathTCG
Algorithme glouton
Principe : Construire une solution pas à pas en sélectionnant à chaque choix local l'option immédiatement la plus rentable.
Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Foundations.