Méthode gloutonne

Méthode gloutonne

Algorithme glouton

Un algorithme glouton est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local, dans l'espoir d'obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins possible de pièces), l'algorithme consistant à répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante est un algorithme glouton. Dans les cas où l'algorithme ne fournit pas systématiquement la solution optimale, il est appelé une heuristique gloutonne.

Sommaire

Algorithme pour la coloration de graphe

Par exemple, l'algorithme suivant n'est qu'une heuristique, car le problème de coloration de graphe est NP-complet.

 Glouton G=(V,E)
 Y=V
 couleur = 0
 Tant que Y n'est pas vide Faire
   couleur ++
   Z=Y
   Tant que Z n'est pas vide Faire
     Choisir v un sommet de Z
     colorier v par couleur
     Y = Y - v
     Z = Z - v - (les voisins de v)
   Fin tant que
 Fin tant que

Exemples

Problème du rendu de monnaie

Suivant le système de pièces, l'algorithme glouton est optimal ou pas. Dans le système de pièces européen (en centimes : 1, 2, 5, 10, 20, 50, 100, 200), où l'algorithme glouton donne la somme suivante pour 37 : 20+10+5+2, on peut montrer que l'algorithme glouton donne toujours une solution optimale.

Dans le système de pièces (1, 3, 4), l'algorithme glouton n'est pas optimal, comme le montre l'exemple simple suivant. Il donne pour 6 : 4+1+1, alors que 3+3 est optimal.

Arbre couvrant minimal

Le problème consiste, dans un graphe non orienté connexe et valué, à trouver un sous-ensemble d'arêtes, formant un arbre, incluant tous les sommets, tel que la somme des poids de chaque arête soit minimale.

Les algorithmes de Prim et de Kruskal sont tous deux des algorithmes gloutons. Le premier consiste à choisir arbitrairement un sommet et à faire croître un arbre à partir de ce sommet. Le second consiste à faire croître une forêt jusqu'à couverture complète. Chaque augmentation se fait de la manière la plus économique possible.

Problème du voyageur de commerce

Une heuristique gloutonne construit une seule solution, par une suite de décisions définitives sans retour arrière, parmi ces méthodes on cite le plus proche voisin, la plus proche insertion, la plus lointaine insertion et la meilleure insertion.

Dans la méthode du plus proche voisin, on part d'un sommet quelconque et à chacune des (n − 1) itérations on relie le dernier sommet atteint au sommet le plus proche au sens coût, puis on relie finalement le dernier sommet au premier sommet choisi.

Dans les méthodes d'insertion, on part d'un cycle réduit à une boucle au départ, à chaque itération on choisit un sommet libre j puis on cherche la position d'insertion i et j de cycle qui minimise l'augmentation totale des coûts; Dans la plus lointaine insertion j est le sommet libre le plus loin du cycle au sens des coûts; dans la plus proche insertion j est le plus proche du cycle; enfin dans la meilleure insertion on teste tous les sommets j non encore insérés et on choisit celui qui donne la plus faible augmentation du coût.

Liens internes

Lien externe

  • Portail des mathématiques Portail des mathématiques
  • Portail de la programmation informatique Portail de la programmation informatique
Ce document provient de « Algorithme glouton ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Méthode gloutonne de Wikipédia en français (auteurs)

См. также в других словарях:

  • Métaheuristique — Une métaheuristique est un algorithme d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence artificielle) pour lesquels on ne… …   Wikipédia en Français

  • Algorithme Glouton — Un algorithme glouton est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local, dans l espoir d obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins… …   Wikipédia en Français

  • Algorithme glouton — Un algorithme glouton est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local, dans l espoir d obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins… …   Wikipédia en Français

  • Problème du rendu de monnaie — Le problème du rendu de monnaie est le suivant : étant donné un système de monnaie (pièces et billets), comment rendre une somme donnée de façon optimale, c est à dire avec le nombre minimal de pièces et billets ? Par exemple, la… …   Wikipédia en Français

  • Désenchantement du monde — Pour les articles homonymes, voir Désenchantement. L expression désenchantement du monde renvoie, dans son sens strict, à un phénomène social : le recul des croyances religieuses ou magiques comme mode d’explication des phénomènes. Dans une… …   Wikipédia en Français

  • 2-opt — En optimisation, 2 opt est un algorithme de recherche locale proposé par Croes en 1958[1] pour résoudre le problème du voyageur de commerce en améliorant une solution initiale. Sommaire 1 L algorithme 1.1 Principe …   Wikipédia en Français

  • Greedy randomized adaptive search procedure — est une métaheuristique, c est à dire un algorithme d’optimisation visant à résoudre des problèmes d’optimisation difficile pour lesquels on ne connaît pas de méthode classique plus efficace. Introduite dans l article Feo and Resende (1989),… …   Wikipédia en Français

  • boyau — [ bwajo ] n. m. • XIIe; bo(i)el 1080; lat. botellus « petite saucisse » 1 ♦ Intestin d un animal (ou, fam. au plur., de l homme). ⇒ entrailles, tripe, viscère. Boyaux de porc, de veau utilisés en charcuterie. ⇒ andouille, boudin, saucisse. Rendre …   Encyclopédie Universelle


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»