Algorithme Glouton (Greedy Algorithm)
1. Algorithme glouton :
Un algorithme glouton est une méthode qui prend une série de décisions basées sur l'optimum
local à chaque étape, dans l'espoir que ces choix mèneront à une solution globale optimale. En
d'autres termes, à chaque itération, l'algorithme sélectionne l'option qui semble être la meilleure à
ce moment précis, sans reconsidérer les décisions précédentes ou envisager les futures étapes.
Caractéristiques principales :
• Choix glouton : À chaque étape, l'algorithme fait le choix qui semble le plus avantageux,
c'est-à-dire celui qui maximise ou minimise une fonction objective locale.
• Optimisation locale : L'algorithme ne cherche pas nécessairement à trouver la solution
optimale globale, mais plutôt une solution qui est suffisamment bonne en se concentrant sur
des sous-problèmes locaux.
• Simples à implémenter : Les algorithmes gloutons sont souvent rapides et faciles à coder
car ils ne nécessitent pas de reconsidérer les décisions passées.
• Efficacité : Bien qu'ils soient rapides, les algorithmes gloutons ne donnent pas toujours la
solution optimale pour tous les problèmes, sauf si le problème a une structure qui garantit
que les choix locaux mènent à une solution optimale globale (comme pour le problème du
rendu de monnaie avec des pièces spécifiques).
Exemples d'applications typiques :
• Problème du rendu de monnaie.
• Problème du sac à dos.
• Problème de l'arbre couvrant minimum (algorithme de Kruskal ou Prim).
• Problème du plus court chemin (algorithme de Dijkstra).
2. . Algorithme par Force Brute (Brute Force Algorithm)
L'algorithme par force brute est une méthode exhaustive qui consiste à tester toutes les solutions
possibles d'un problème pour en identifier la meilleure. Il garantit toujours d'obtenir une solution
optimale, car il explore toutes les combinaisons, mais il est souvent très coûteux en temps de calcul,
notamment pour des problèmes avec de grandes entrées ou un grand nombre de solutions
possibles.
Caractéristiques principales :
• Exhaustivité : L'algorithme explore toutes les combinaisons et configurations possibles du
problème, ce qui en fait un processus complet mais souvent très lent.
• Solution optimale : Étant donné qu'il teste toutes les solutions, la force brute garantit
toujours de trouver la solution optimale.
• Complexité élevée : La complexité d'un algorithme par force brute est souvent exponentielle
ou factorielle, car il doit examiner chaque combinaison possible. Cela le rend impraticable
pour des problèmes avec un grand espace de solutions.
• Facilité d'implémentation : Bien que coûteuse en termes de performance, la force brute est
souvent facile à comprendre et à implémenter car elle repose sur l'exploration complète des
solutions.
Exemples d'applications typiques :
• Résolution de puzzles (ex. Sudoku, échecs).
• Problème du sac à dos (version discrète).
• Recherche dans un texte (toutes les combinaisons de sous-chaînes).
• Résolution du problème de voyageur de commerce (TSP) en énumérant tous les circuits
possibles.
3. Le problème de rendu de monnaie
Un des grands classiques est le problème du rendu de monnaie où l'on souhaite rendre une
somme en utilisant le moins de pièces (ou de billets) possibles. Le principe de l'algorithme consiste
à répéter le choix de la pièce de plus grande valeur qui ne dépasse pas la somme restante.
Remarque :
On dit qu'il s'agit d'un algorithme glouton car il choisit la pièce la plus grosse à chaque étape sans
réfléchir à la suite.
Exemple avec le système de pièces européen :
Rendre la somme de 8€ Solution optimale Solution non optimale
Avec le système de pièces européen, l’algorithme glouton donne toujours un choix optimal.
Mais que se passe-t-il, s’il on utilise un autre monnayeur avec des pièces différentes ?
Rendre la somme de 6€ Solution optimale Solution non optimale
Algorithme pseudo code Python
Fonction renduMonnaie (somme en entier, pièces : liste des
pièces du monnayeur dans l’odre décroissant) : liste des
pièces choisies
n←longueur de la liste de pièces
initialiser à zéro la liste choisie de dimension n
Pour i de 0 à n-1 par pas de 1
Tant que somme>= pieces[i]
somme←somme-pieces[i]
choisies[i]← choisies[i]+1
fin tant
que fin pour
retourner choisiesTant que somme>=
pieces[i] somme←somme-pieces[i]
choisies[i]← choisies[i]+1
fin tant que fin pour
retourner choisies
Résultat dans la console
pieces=[500,200,100,50,20,10,5,2,1] Les pièces choisies sont
somme=780 [1, 1, 0, 1, 1, 1, 0, 0, 0]
print('Les pièces choisies sont')
print(renduMonnaie(somme,pieces))
Vérification :
Pièces 500 200 100 50 20 10 5 2 1
Choisies 1 1 0 1 1 1 0 0 0
Soit 780 centimes, l’algorithme fonctionne et est optimal avec le système de pièces européen
Test N°2
Résultat dans la console
pieces=[4,3,1] somme=6 Les pièces choisies sont
print('Les pièces choisies sont') [1, 0, 2]
print(renduMonnaie(somme,pieces))
Vérification :
Pièces 4 3 1
Choisies 1 0 2
Soit 6 euros, l’algorithme fonctionne mais n’est pas optimal car on aurait pu rendre 2 pièces de
3€
Test N°3
Résultat dans la console
pieces=[10,5,2] somme=31 Les pièces choisies sont
print('Les pièces choisies sont') [3, 0, 0]
print(renduMonnaie(somme,pieces))
Vérification :
Pièces 10 5 2
Choisies 3 0 0
Soit 30 euros, l’algorithme ne fonctionne plus car il manque une pièce de 1 euro.
4. Le problème Du sac à dos
Le problème du sac à dos (knapsack problem) est aussi un problème d’optimisation. Il permet de
résoudre le problème du remplissage d’un sac à dos. On dispose pour cela de plusieurs objets
(chaque objet possède une valeur et un poids). Seulement le sac ne peut pas contenir plus d’un
certain poids. Le but des de choisir judicieusement les objets afin de maximiser la valeur des objets
sans dépasser le poids maximum. L’algorithme glouton va choisir à chaque étape du remplissage
l’objet de plus grande valeur. On répète les étapes du remplissage juste avant que le poids maximal
soit atteint. Exemple :
Matériel à emmener dans un sac de 4.7KG Valeur et poids Emporté (oui/non)
Valeur : 2
Poids : 1
Valeur : 5
Poids : 0.5
Valeur : 1
Poids : 0.2
Valeur : 3
Poids : 4
Algorithme pseudo code Python
Fonction remplirSac (objets : liste des objets dans l’ordre
décroissant,
poidsMax : en décimal) : liste des objets
choisis
P←0
n←longueur de la liste des objets
initialiser à zéro la liste objetschoisis de dimension n
Pour i de 0 à n-1 par pas de 1
Si p+objets[i][1]<= poidsMax
alors
objetsChoisis[i]←1
p ← p +
objets[i][1]
fin
si fin pour
retourner objetschoisis
Test
Attention : il faudra trier las objets par ordre décroissant de valeur avant d’appeler la fonction
remplirSac(objets,poidsMax)
Résultat dans la console
objets=[[2,1],[5,0.5],[1,0.2],[3,4]] [[5, 0.5], [3, 4], [2, 1], [1, 0.2]]
objets=list(reversed(sorted(objets))) print(objets) Les objets choisis sont [1, 1, 0, 1]
poidsMax=4.7
print('Les objets choisis sont')
print(remplirSac(objets,poidsMax))
Vérification :
Jumelles Tente Gourde d’eau Carte
Objets
Objets choisis 1 1 0 1
L’algorithme choisi bien les articles selon notre prévision.
Comparaison des Résultats et Analyse
Approche Gloutonne Approche par Force Brute
Problème
(Solution Manuelle) (Solution Manuelle)
Rendu de Garantit la solution optimale mais coûteuse
Solution rapide mais optimale
Monnaie en calculs
Sac à Dos Donne de bons résultats, simple à Garantit une solution optimale, mais
Fractionné calculer beaucoup plus coûteuse
Lent, O(2n) surtout pour des grands
Complexité Rapide, O((n logn)
ensembles
