Approche gloutonne

Une approche gloutonne consiste à construire une solution en effectuant une série de choix locaux optimaux, sans revenir en arrière. Ces choix sont basés sur un critère de sélection qui maximise (ou minimise) un objectif à chaque étape. Bien que rapide et simple à implémenter, cette méthode n'assure pas toujours d'atteindre une solution optimale.

Solutions optimales et d'approximation

Une solution optimale est la meilleure solution possible pour répondre à un problème.

Une solution d'approximation vise à être proche de l'optimum, tout en réduisant la complexité computationnelle. L'approche gloutonne est particulièrement utile pour les problèmes NP-difficiles, où trouver une solution exacte est souvent irréaliste.

L'approche gloutonne offre alors un bon compromis entre performance et qualité de la solution.

Illustrations

Problème du sac à dos

Dans ce problème, on dispose d'un sac avec une capacité donnée, et d'objets ayant chacun une masse et une valeur. L'objectif est de maximiser la valeur totale en respectant la capacité du sac.

Une approche gloutonne permet d'obtenir un algorithme qui va d'abord trier les objets par valeur, par masse ou par ratio valeur/poids. Les objets seront ensuite ajoutés au sac dans leur ordre de tri. Cet algorithme ne renvoie pas toujours une solution optimale, mais il fournit généralement une solution convenable en un temps contenu.

Problème de couverture des sommets

Dans un graphe, le problème de couverture des sommets consiste à trouver le plus petit ensemble de sommets couvrant toutes les arêtes.

L'approche gloutonne choisit à chaque étape le sommet couvrant le plus grand nombre d'arêtes non couvertes, jusqu'à ce que toutes les arêtes soient couvertes. Cela donne une approximation efficace dans la pratique.

Problème du voyageur de commerce (TSP)

Pour un voyageur devant visiter plusieurs villes avec le coût minimal, une approche gloutonne part d'une ville et choisit à chaque étape la ville la plus proche non visitée. Bien que cette méthode ne garantisse pas une solution optimale, elle est rapide et fournit un bon point de départ pour des optimisations ultérieures.