Méthodes de résolution de problèmes

3. Résolution de problèmes

3.3. Algorithme glouton (greedy algorithm)

  • Un algorithme glouton fait, étape par étape, le choix d’un optimum local.
  • A chaque itération, on fixe la valeur d'une des variables décrivant le problème sans remettre en cause les choix antérieurs.
  • Le principe est donc de partir d'une solution incomplète que l'on complète de proche en proche en effectuant des choix définitifs : à chaque étape, on traite une partie des variables sur lesquelles on ne revient plus.
  • Conception facile à mettre en œuvre.
  • Rapides mais ne fournissent pas toujours la solution optimale au problème donné.
  • Construit une solution pas à pas sans revenir sur ses décisions,
  • Obtenir un résultat optimum global
  • Effectue à chaque étape le choix qui semble le meilleur.

Les algorithmes gloutons utilisent une fonction d’évaluation f(n) pour chaque nœud


•Fonction d’évaluation

f(n) = h(n) (heuristique)    où   

•f(n)= estimation du coût de n à but
•h(n) = distance en ligne droite de n à but

Exemple:
On considère le problème où l’on doit rendre la monnaie pour une certaine somme S avec le moins possible de pièces de monnaies.


Sachant qu'on a des pièces de 1, 2, 5, 10, 20.
Quelle est la  solution optimale?
Avec S=26

  1. On va tout d'abord trier les types de pièces par valeurs décroissantes.
  2. Pour chaque valeur de pièce, maximiser le nombre de pièces choisies.
  3. Répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante tant que celle-ci n’est pas nulle.

Donc, pour  S=26 (3 pièces), on va obtenir:

  • 1 pièce de 20
  • 1 pièce de 5
  • 1 pièce de 1


Maintenant, si on veut rendre la somme S = 26  en pièces de 7, 6, 1. Quelle est la solution optimale?

•Algorithme glouton (8 pièces)
    • 3 Pièces de 7
    •  5 pièces de 1
•Solution optimale (4 pièces)
    • 2 pièces de 7
    • 2 pièces de 6