5 - Algorithmes gloutons
Nous allons voir aujourd'hui un nouveau type d'algorithme permettant de répondre à des problèmes complexes.
La stratégie la plus évidente pour résoudre un problème compliqué est la force brute :
Moyen n°1 : le premier moyen est la force brute.
- Principe : on y va franchement, on calcule tout, quitte à calculer les choses plusieurs fois, voire à calculer des choses qui ne servent en rien pour trouver la solution.
- Type de problème : tous les problèmes à priori.
- Problème : c'est beaucoup trop long si le problème est vraiment complexe et qu'on ai besoin de faire beaucoup beaucoup de calculs.
Moyen n°2 : aujourd'hui, nous allons voir qu'on peut "tricher" en utilisant la stratégie gloutonne.
- Principe : on ne regarde pas le problème dans sa totalité. On prend une décision purement locale, de façon définitive et sans se soucier de ce que va devenir le problème restant à traiter.
- Type de problème : ceux pour lequels on peut trouver plusieurs solutions, optimales ou pas.
Nous allons voir comme Mr Glouton peut atteindre la case en bas à droite en mangeant le plus mal possible.
Comme on le voit, la taille du problème à traiter diminue à chaque décision.
Logiciel nécessaire pour l'activité : Python 3 : Thonny, IDLE ou le site repl.it ...
Prérequis : Algorithme : savoir prouver la terminaison d'un algorithme (algo 2, 3 ou 4)
Evaluation ✎ : questions 06-07-13-14-18-19-20
1 - La problématique des problèmes complexes
Nous avions déjà parlé des problèmes NP lors de l'activité n°1. NP vient de Non déterministe Polynomial. Il s'agit concrètement de problèmes par lesquels
- le coût de la résolution par force brute est plus complexe qu'un coût polynomial
- on peut trouver la meilleur solution si on fait les bons choix par hasard et qu'on a de la chance
- on peut vérifier qu'une solution qu'on vous propose est valide ou pas avec un coût polynomial.
Pour rappel
Différents cooûts rencontrés
Voici un classement des coût, de la catégorie la plus simple à la plus complexe.
Coût constante : Θ(1)
Cela veut dire que quelque soit le nombre de n de données, la réponse est fournie après le même délai.
Coût logarithmique : Θ(log (n))
Nous travaillerons avec le log2 mais il en existe d'autres.
Le temps de traitement d'un ensemble d'un million de données est lié à
log10(1000000) = log10(106) = 6.
Le temps de traitement d'un ensemble d'un milliard de données est lié à
log10(1000000000) = log10(109) = 9.
Seulement 3 opérations en plus par rapport au million. Pas mal.
Exemple vu dans "Alice déménage" : recherche par dichotomie dans un ensemble de cartons triés par ordre croissant ou décroissant.
Coût polynomial : Θ(nk)
Il s'agit des coûts dont l'expression de la complématique peut s'exprimer comme ci-dessus. Plus cas est petit, plus le coût est bon, plus k est grand plus le coût est médiocre.
k = 1/2 : on a du Θ(n1/2), on parle de coût racinaire.
k = 1 : on a du Θ(n), on parle de coût linéaire.
k = 2 : on a du Θ(n2), on parle de coût quadratique.
k = 3 : on a du Θ(n3), on parle de coût cubique.
...
Exemple vu dans "Alice déménage" : trouver un carton parmi des cartons ordonnés (en ligne plutôt que posés au hasard) est à coût linéaire.
Exemple vu dans "Alice déménage" : ranger les cartons un par un dans le camion en les aménant dans un ordre particulier est à coût quadratique.
Coût exponentiel : Θ(kn)
Encore pire que le polynomiale. Regardons le cas d'un algorithme en Θ(2n)
>>> 2**100
1267650600228229401496703205376
>>> 2**1000
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
Vous devriez comprendre pourquoi on considère qu'un algorithme en complexité exponentielle n'est pas exploitable. Il y a pourtant encore pire avec le cas ci-dessous...
Complexité factorielle : Θ(n!)
>>> import math
>>> math.factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
>>> math.factorial(1000)
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
On voit que les deux derniers cas vont faire travailler l'ordinateur sur une durée non exploitable. S'il faut attendre 200 ans, c'est trop long.
Nous allons justement voir aujourd'hui des problèmes de ce type. Et nous y répondrons en un temps raisonnable, avec une technique un peu particulière.
2 - Problème du voyageur de commerce
Imaginons le problème suivant : vous devez organiser la tournée de votre commercial. Il doit passer dans toutes les villes sous sa responsabilité (une fois uniquement) et revenir à son point de départ (Lille pour notre exemple). Pour limiter les frais, il faut définir le trajet le moins long au total.
Nous allons nous limiter à 6 villes uniquement ici.
Voici un tableau récapitulant les distances entre ces 6 villes.
| Brest | Bordeaux | Lille | Lyon | Marseille | Paris | |
|---|---|---|---|---|---|---|
| Brest | - | 598 | 708 | 872 | 1130 | 572 |
| Bordeaux | 598 | - | 802 | 520 | 637 | 554 |
| Lille | 708 | 802 | - | 650 | 1002 | 225 |
| Lyon | 872 | 520 | 650 | - | 367 | 465 |
| Marseille | 1130 | 637 | 1002 | 367 | - | 777 |
| Paris | 572 | 554 | 225 | 465 | 777 | - |
Nous pourrions choisir la ville de départ parmi la liste des 6 villes. Il y a donc 6 choix de lieux de départ.
01° Partons de Lille. Combien de destinations différentes peut-on choisir ?
...CORRECTION...
Partant de Lille, on peut choisir 5 villes : Brest, Bordeaux, Lyon, Marseille et Paris.
02° Partant de Lille, on choisit Bordeaux. Combien de destinations différentes peut-on choisir ensuite ?
...CORRECTION...
Après Lille et Bordeaux, il reste 4 villes : Brest, Lyon, Marseille et Paris.
03° Après avoir choisi Lille - Bordeaux - Brest, combien de destinations différentes peut-on choisir ensuite ?
...CORRECTION...
Il reste 3 villes : Lyon, Marseille et Paris.
Normalement, vous avez compris le principe 🙂 !
04° Combien de possibilités d'itinéaires différents va-t-on avoir en partant d'une première ville aléatoire pour aller jusqu'à la 6e ville ? Faire le calcul.
...CORRECTION...
On choisit une première ville parmi 6 possibilités.
La deuxième parmi 5 possibilités.
La troisième parmi 4 possibilités.
On calcule donc le nombre nb d'itinéraires différents de cette façon :
nb = 6*5*4*3*2*1
Il s'agit d'un calcul de factoriel.
On pourra donc noter nb = 6!
Et le résultat est nb = 720
Oui mais... Ici, il s'agit de trouver un chemin fermé, c'est un cycle.
1er simplification : le point de départ n'a aucune importance puisqu'on passe successivement dans toutes les villes et qu'on revient au point de départ.
2e simplification : le sens de parcours du cycle n'a pas d'importance non plus. Dans les deux cas, on fera le tour des 6 villes. Qu'on fasse Lyon-Lille-... ou Lille-Lyon-... ne changera rien à la distance parcourue.
05° Combien de possibilités doit-on vraiment calculer en tenant compte des deux remarques précédentes ?
...CORRECTION...
On choisit un "point" de départ.
La deuxième ville parmi 5 possibilités.
La troisième parmi 4 possibilités.
Avec 6 villes, on calcule donc le nombre nb d'itinéraires différentes de cette façon :
nb = 5*4*3*2*1
Il s'agit d'un calcul de factoriel.
On pourra donc noter nb = 5!
Dans la mesure, où nous avons n villes, la formule serait donc nb = (n-1)!
Dernière simplification : on peut diviser ce nombre par deux puisqu'on trouvera forcément un second parcours qui ne différe que par le sens dans lequel on rencontre les villes : Paris - Lille - Marseille - Paris ou Marseille - Lille - Paris - Marseille, c'est pareil.
Dans la mesure, où nous avons n villes, la formule serait donc nb = (n-1)! / 2
Pour n villes, on obtient du coup 60 parcours réellement différents. C'est mieux.
Nous pourrions encore supprimer certains parcours similaires mais nous allons en rester là.
C'est lourd à calculer pour un humain mais c'est facile et rapide pour un ordinateur.
Regardons comment faire le calcul avec Python avec, par exemple, 10 villes ? C'est pas énorme 10 villes...
Voici comment on calcule nb = (10-1)! / 2 avec Python :
>>> import math
>>> math.factorial(10-1) // 2
181440
Et oui, plus de 180 000 possibilités différentes. Pour un problème comportant juste 10 villes...
Si le problème avait été plus simple, disons de type exponentielle 2, on aurait eu ceci :
>>> 2**10
1024
C'est déjà mieux.
Si on avait un problème en log2, ça aurait donné ceci :
>>> import math
>>> math.log2(10)
3.321928094887362
Encore mieux.
✎ 06° Combien de possibilités d'itinéaires différents va-t-on avoir pour 12 villes ? Juste deux petites villes en plus...
Rappel : nb = (n-1)! / 2
3 - Résolution par force brute
Avant de passer aux algorithmes gloutons, voyons comment résoudre ce problème par force brute : nous allons faire tous les calculs et ne garder que le meilleur.
Ici, avec 6 villes, il faut donc tester les 60 possibilités une par une. Avec 12 villes, on passe à 20 millions de possibilités.
C'est faisable avec 6 villes.
Le trajet optimal sera réalisé avec le parcours suivant (dans un sens ou dans l'autre) :
Brest-Bordeaux-Marseille-Lyon-Paris-Lille-Brest en 3000 km
Brest-Lille-Paris-Lyon-Marseille-Bordeaux-Brest en 3000 km
L'itinéraire de la partie précédente était correct mais de moins bonne qualité. Il vaut mieux faire celui proposé ici (si on a réussi à le trouver !)
✎ 07° Choisir un autre itinéraire et calculer à la main la distance parcourue. Le tableau des distances est fourni ci-dessous. Vérifier qu'on obtient pas moins qu'avec le trajet optimal.
| Brest | Bordeaux | Lille | Lyon | Marseille | Paris | |
|---|---|---|---|---|---|---|
| Brest | - | 598 | 708 | 872 | 1130 | 572 |
| Bordeaux | 598 | - | 802 | 520 | 637 | 554 |
| Lille | 708 | 802 | - | 650 | 1002 | 225 |
| Lyon | 872 | 520 | 650 | - | 367 | 465 |
| Marseille | 1130 | 637 | 1002 | 367 | - | 777 |
| Paris | 572 | 554 | 225 | 465 | 777 | - |
4 - Algorithme Glouton
Nous avons vu que la force brute ne permet pas de résoudre (en un temps raisonnable) le problème du voyageur de commerce lorsqu'on augmente le nombre de villes.
Maintenant que vous avez manipulé ce problème et vu à quel point il est complexe à résoudre, nous allons voir comment faire autrement.
Principe des algorithmes gloutons
Principe de la stratégie
On résoud le problème en ne regardant qu'une partie des données à la fois. On fait alors un choix local qui va réduire la taille du problème qu'il reste à traiter. On fait cela plusieurs fois, le problème devenant de plus en plus petit. On espère ainsi aboutir à une solution satisfaisante.
Type de problèmes traités par cette stratégie
On utilise ce type d'algorithme lorsqu'on est confronté à un problème d'optimisation pour lequel la recherche de la solution optimale est difficile.
En algorithmique, difficile veut dire qu'on ne peut pas résoudre le problème en un temps raisonnable. Habituellement cela veut dire que la complexité est plus que polynomiale.
Pour pouvoir utiliser un algorithme glouton, il faut qu'on puisse fournir de multiples solutions, certaines optimales, certaines bonnes et d'autres plutôt mauvaises.
ATTENTION : s'il n'y a qu'une solution UNIQUE, ce n'est pas de l'optimisation ! On utilisera d'autres méthodes de résolution.
Exemple d'algorithme glouton avec la recherche du point de haute altitude
Imaginons qu'on cherche à trouver un point de haute altitude dans un espace en 2D ne comportant aucun terrain plat (pour simplifier la démarche).
L'approche gloutonne peut se résumer au choix local suivant : on se dirige systématiquement du côté qui grimpe le plus. Si cela descend des deux côtés, on s'arrête.
Premier exemple : on part d'un point A dont on ne connait que le voisinage proche. Voir l'image ci-dessous.
Remarquez bien qu'on ne regarde pas la totalité du problème : on se limite à un choix local et facile à faire : ça grimpe à gauche et pas à droite : on décide donc de partir à gauche. Nous arrivons au point n°2.
Que faire ?
Ca grimpe à gauche et pas à droite : on part à droite. Nous arrivons au point 3.
Une fois sur la position 3, on obtient la même configuration : on prend donc la même décision de continuer à gauche pour arriver au point 4.
Sur la position 4, on voit que ça descend à gauche et à droite : on stoppe. Nous sommes arrivés au point final.
Comme vous le voyez, nous n'avons aucune vision globale du problème : notre algorithme prend ses décisions uniquement en fonction de la situation locale actuelle.
Rien n'est gardé en mémoire et on ne regarde qu'une partie du problème à la fois.
Et voici le problème réel, en vision globale.
On voit donc que l'algorithme glouton est bien parvenu à fournir une réponse rapidement. Nous sommes bien sur un point-haut (l'un des maximums), mais il ne s'agit pas de la solution optimale : nous ne sommes pas sur le maximum absolu.
Voici deux autres exemples qui illustrent le fait qu'on trouve bien une solution. Parfois, la solution est optimale. Parfois non.
Comme vous le voyez, le principe est donc de prendre des décisions en ne regardant qu'un petit bout du problème. On optimise les réponses localement en espérant que cela mène à une solution globale acceptable.
C'est plus facile et plus rapide. Par contre, on n'obtient pas nécessairement la "meilleure" réponse. Nous obtenons parfois un maximum local et pas le maximum absolu.
On dit que l'algorithme glouton fournit une heuristique : une méthode fournissant rapidement une solution mais cette solution ne sera pas nécessairement optimale.
Appliquons une stratégie gloutonne à notre voyageur de commerce.
Voici le choix local que nous allons toujours privilégier en espérant que cela nous mène à une solution globale correcte : nous allons systématiquement choisir la ville non-visitée la plus proche. Point.
Facile non ?
08° On décide de partir de Lyon. Choisir la ville suivante en prenant la ville la plus proche non encore visitée. Calculer la distance parcourue.
| Brest | Bordeaux | Lille | Lyon | Marseille | Paris | |
|---|---|---|---|---|---|---|
| Brest | - | 598 | 708 | 872 | 1130 | 572 |
| Bordeaux | 598 | - | 802 | 520 | 637 | 554 |
| Lille | 708 | 802 | - | 650 | 1002 | 225 |
| Lyon | 872 | 520 | 650 | - | 367 | 465 |
| Marseille | 1130 | 637 | 1002 | 367 | - | 777 |
| Paris | 572 | 554 | 225 | 465 | 777 | - |
...CORRECTION...
On prendra Marseilles puisque Lyon-Marseille vaut 367 km. Marseille est la ville disponible la plus proche depuis Lyon.
09° On a fait Lyon-Marseille. Quelle ville choisir ensuite ?
| Brest | Bordeaux | Lille | Lyon | Marseille | Paris | |
|---|---|---|---|---|---|---|
| Brest | - | 598 | 708 | 872 | 1130 | 572 |
| Bordeaux | 598 | - | 802 | 520 | 637 | 554 |
| Lille | 708 | 802 | - | 650 | 1002 | 225 |
| Lyon | 872 | 520 | 650 | - | 367 | 465 |
| Marseille | 1130 | 637 | 1002 | 367 | - | 777 |
| Paris | 572 | 554 | 225 | 465 | 777 | - |
...CORRECTION...
On prendra Bordeaux puisque Marseille-Bordeaux vaut 637 km. Lyon est plus proche de Marseilles mais nous y sommes déjà passés.
Au total, on a donc d = 367 + 637 km.
10° On a fait Lyon-Marseille-Bordeaux. Quelle ville choisir ensuite ?
| Brest | Bordeaux | Lille | Lyon | Marseille | Paris | |
|---|---|---|---|---|---|---|
| Brest | - | 598 | 708 | 872 | 1130 | 572 |
| Bordeaux | 598 | - | 802 | 520 | 637 | 554 |
| Lille | 708 | 802 | - | 650 | 1002 | 225 |
| Lyon | 872 | 520 | 650 | - | 367 | 465 |
| Marseille | 1130 | 637 | 1002 | 367 | - | 777 |
| Paris | 572 | 554 | 225 | 465 | 777 | - |
...CORRECTION...
Depuis Bordeaux, il faut choisir entre Brest, Paris et Lille.
On partira à Paris, 554 km.
Au total, on a donc d = 367 + 637 + 554 km.
11° On a fait Lyon-Marseille-Bordeaux-Paris. Quelle ville choisir ensuite ?
| Brest | Bordeaux | Lille | Lyon | Marseille | Paris | |
|---|---|---|---|---|---|---|
| Brest | - | 598 | 708 | 872 | 1130 | 572 |
| Bordeaux | 598 | - | 802 | 520 | 637 | 554 |
| Lille | 708 | 802 | - | 650 | 1002 | 225 |
| Lyon | 872 | 520 | 650 | - | 367 | 465 |
| Marseille | 1130 | 637 | 1002 | 367 | - | 777 |
| Paris | 572 | 554 | 225 | 465 | 777 | - |
...CORRECTION...
Depuis Paris, il reste donc Lille ou Brest.
On partira à Lille, 225 km.
Au total, on a donc d = 367 + 637 + 554 + 225 km.
A partir de là, c'est fini. On fait Lille-Brest (c'est la seule destination disponible) puis Brest-Lyon pour revenir au point de départ.
Ca donne d = 367 + 637 + 554 + 225 + 708 + 872 km
Au total d = 3363 km.
- Désavantage : c'est moins bien que la solution optimale de 3000 km.
- Avantage : avec plus de villes que sur notre exemple, le programme en force brute tournerait encore longtemps, longtemps, longtemps...
5 - Rendu de monnaie
Autre problème typique qu'on peut résoudre avec la stratégie gloutonne : le rendu de monnaie.
Imaginons une somme de 5,50 euros à rendre.
Nous avons à disposition le billet de 5 euros, la pièce de 2 euros, la pièce de 1 euro, la pièce de 50 cents, la pièce de 20 cents, la pièce de 10 cents, la pièce de 5 cents.
Pour le transformer en problème d'optimisation, il faut rajouter une façon de classer la qualité des solutions : on veut une solution pour laquelle on rend le moins de pièces ou de billets possibles.
Pour un humain, ça ne pose pas de problème : un billet de 5 euros et une pièce de 50 cents.
Mais vous vous rendez bien compte des possibilités possibles à comparer pour une machine...
Nous allons donc appliquer une stratégie gloutonne en choississant ce choix local optimal : toujours compléter la somme à rendre avec le billet ou la pièce la plus grande utilisable.
12° En appliquant ce principe, que doit-on donner si on doit rendre 29 euros à l'aide de billets de 20 euros, 10 euros et 5 euros et de pièces de 2 euros et 1 euro ?
...CORRECTION...
On part de 29 euros.
On choisit de sélectionner des billets de 20 euros. Combien ? Un seul.
On rend un billet de 20 euros. Il reste 9 euros à rendre.
On choisit alors les billets de 5 euros. Combien ? Un seul.
On rend 20 euros et 5 euros. Il reste 4 euros à rembourser.
On choisit les pièces de 2 euros. Combien ? 2.
On rend donc un billet de 20 euros, un billet de 5 euros et deux pièces de 2 euros.
✎ 13° Fournir la réponse de notre stratégie gloutonne si on doit rendre 10 euros en choissant dans l'ensemble { 5, 2, 1 }. Est-ce la solution optimale pour notre ensemble de pièces disponibles ?
✎ 14° Fournir la réponse de notre stratégie gloutonne si on doit rendre 10 euros avec l'ensemble { 8, 5, 1 }. Proposer une meilleure solution en utilisant votre cerveau et pas la stratégie gloutonne.
Et voilà. Ca fonctionne toujours pourvu qu'on ai une pièce correspondant à la plus petite somme à rendre mais ça ne donne pas toujours la solution optimale. De toutes manières, évaluer toutes les possibilités ne devrait pas faire diminuer significativement le nombre de pièces à rendre.
6 - Rendu de monnaie avec Python
Nous allons finir en appliquant la stratégie gloutonne du rendu de monnaie à Python.
On commencera par créer un tableau trié en ordre décroissant les_choix regroupant les sommes qu'on peut rendre et une fonction rendre() qui possède deux paramètres :
- le paramètre a_rendre pour récupérer la somme qu'il faudra rendre
- le paramètre choix pour récupérer le tableau trié des choix de billets ou pièces disponibles, du plus grand au plus petit.
La fonction rendre() devra renvoyer un tableau contenant les éléments à rendre. Par exemple [100, 10, 5, 2, 2] pour rendre 119 euros.
Voici le prototype : rendre(a_rendre:int, choix:list) -> list
Voici les instructions incomplétes correspondantes :
1
2
3
4
5 | les_choix = [100, 50, 20, 10, 5, 2, 1]
def rendre(a_rendre, choix=les_choix):
reponse = []
return reponse
|
On remarquera que le deuxième paramètre de la fonction, choix possède une valeur par défaut : nous ne sommes pas obligés de lui transmettre ce tableau. Si on ne lui transmet rien, il va alors remplir ce paramètre avec la variable les_choix.
On pourra donc activer l'appel de notre fonction simplement de cette façon pour rendre 12 euros :
>>> rendre(12)
Mais on pourra également fournir une valeur pour le paramètre choix :
>>> rendre(12, [50, 20, 10, 1])
>>> rendre(12, les_choix)
Voici l'algorithme que vous allez devoir créer en Python :
Algorithme glouton du rendu de monnaie
Description des entrées / sortie
ENTREES:a_rendre: la somme à rendre.choix: un tableau trié en ordre décroissant contenant l'ensemble des billets ou pièces permettant de rendre la monnaie. Votre tableau doit contenir une valeur finale permettant de rendre la plus petite somme possible.- (optionnelle selon les langages d'implémentation):
longueur, le nombre d'éléments dans le tableau SORTIE: un tableau contenant les éléments (billets ou pièces) à rendre.
Algorithme commenté
- JAMAIS DE TEST D'EGALITE ENTRE DEUX FLOAT !
- VIGILANCE SUR LES CALCULS REPETIFS
- phrase rapide d'explication,
- préconditions (sur les paramètres d'entrée),
- la ou les post-conditions (sur la réponse)
- au moins un exemple permettant de comprendre son fonctionnement et de l'utiliser éventuellement pour un doctest.
- faire des choix locaux qu'on pense efficaces
- pour résoudre le problème au niveau global.
- Point de haute altitude : on part du côté voisin qui monte le plus
- Voyageur de commerce : on choisit la ville non visitée la plus proche
- Rendu de monnaie : on choisit le billet ou la pièce la plus grosse encore utilisable
reponse ← []
ce tableau vide initialement va contenir la réponse
reste ← a_rendre
reste va contenir ce qu'on doit encore rendre, au départ elle contient donc a_rendre
i ← 0
on va commencer par le premier élément fourni dans choix, l'élément de plus grande valeur
TANT QUE reste est strictement supérieure 0
SI reste est supérieure ou égale à choix[i]
on peut rendre une partie de l'argent avec le billet ou la pièce choix[i]
reste ← reste - choix[i]
on rajoute choix[i] dans reponse
SINON
choix[i] est plus grand que la somme à rendre, il faut passer au billet ou la pièce suivante
i ← i + 1
Fin Si
Fin Tant que
Si on arrive ici, c'est qu'on est sorti du tant que : reste valait 0
Renvoyer reponse
15° Compléter la fonction Python ci-dessous (en modifiant les zones surlignées) pour qu'elle applique correctement l'algorithme ci-dessus.
1
2
3
4
5
6
7
8
9
10
11
12
13 | les_choix = [100, 50, 20, 10, 5, 2, 1]
def rendre(a_rendre, choix=les_choix):
reponse = []
reste = a_rendre
i = 0
while True:
if True:
pass
pass
else:
pass
return reponse
|
Vous trouverez ci-dessous quelques indications vous permettant d'avancer.
Rappel : pour rajouter à élément à un tableau, il faut utiliser la méthode append.
>>> fruits = ['Ananas']
>>> fruits.append('Banane')
>>> fruits
['Ananas', 'Banane']
Avertissement : je ne veux voir que choix dans le corps de votre fonction. N'utilisez pas la variable globale mes_choix. Elle sert uniquement de valeur par défaut au paramètre choix.
Exemple de résultats attendus (je n'ai pas mis de doctest, car vous aurez à le faire dans quelques questions) :
>>> rendre(15)
[10, 5]
>>> rendre(17)
[10, 5, 2]
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13 | les_choix = [100, 50, 20, 10, 5, 2, 1]
def rendre(a_rendre, choix=les_choix):
reponse = []
reste = a_rendre
i = 0
while reste > 0:
if reste >= choix[i]:
reste = reste - choix[i]
reponse.append(choix[i])
else:
i = i + 1
return reponse
|
Analysons un peu le programme réalisé.
En apparence, puisque la condition du TANT QUE est une condition du type while un > 0 et que reste va décroître, on pourrait croire qu'elle se termine bien à tous les cas. Erreur.
16° Répondre aux trois questions suivantes qui traitent des erreurs d'exécution possibles.
Question 1 : Le programme pourrait-il fonctionner avec des euros entiers si nous avions le tableau suivant (dans lequel il manque juste la pièce d'un euro) : les_choix = [100, 50, 20, 10, 5, 2]) ? Faire le test avec rendre(13) et rendre(12) pour tenter de voir s'il peut tourner en boucle.
Question 2 : Que va-t-il se passer si on demande rendre(17.5) ? Que pourrait-on faire pour permettre au système de gérer les centimes ?
Question 3 : Le programme pourrait-il fonctionner avec des cents (en rajoutant les cents dans le tableau bien entendu : les_choix = [100, 50, 20, 10, 5, 2, 1, 0.50, 0.20, 0.10, 0.05, 0.02, 0.01]) ? Faire le test avec rendre(17.50) et rendre(17.15) pour tenter de voir s'il peut tourner à chaque fois.
...CORRECTION...
Réponse 1 : Avec le tableau ci-dessous, nous allons encore provoquer une erreur : nous allons encore augmenter l'indice après la pièce de 2 euros. Or, il n'y a plus rien derrière...
1 | les_choix = [100, 50, 20, 10, 5, 2]
|
Si on doit rendre 13 euros, il faut rendre 10 + 2 + 1. Or, le 1 n'existe pas...
Réponse 2 : Si on demande de rendre 17.5 euros, l'algorithme vaut sélectionner 10 euros, 5 euros, 2 euros. Ensuite, puisque 1 euro est supérieur à 0.5 euro, il va continuer à augmenter l'indice et va finir par demander un indice incorrect. La boucle TANT QUE ne s'arrêterait pas sinon. Il reste toujours 50 cents à rendre. C'est l'erreur d'indice qui provoque l'erreur, pas l'arrêt de la boucle.
Réponse 3 : On retrouve le problème de l'égalité sur les flottants.
Vous pouvez rajouter un print pour voir le contenu du reste juste sous le while.
Avec 17.50 euros :
>>> rendre(17.5)
17.5
17.5
17.5
17.5
7.5
7.5
2.5
0.5
0.5
0.5
[10, 5, 2, 0.5]
0.50 euros ne pose pas de problème car c'est une puissance de deux : l'ordinateur parvient à faire le calcul exact.
Par contre, 0.20 ou 0.10 ne sont pas encodés de façon exacte.
Avec 17.15 euros :
>>> rendre(17.15)
17.15
17.15
17.15
17.15
7.149999999999999
7.149999999999999
2.1499999999999986
2.1499999999999986
0.14999999999999858
0.14999999999999858
0.14999999999999858
0.14999999999999858
0.14999999999999858
0.04999999999999857
0.04999999999999857
0.04999999999999857
0.03999999999999857
0.02999999999999857
0.019999999999998568
0.009999999999998567
0.009999999999998567
if reste >= choix[i] :
IndexError: list index out of range
Et oui : le reste réel vaut 0.0 mais à force de faire de mauvais stockage, il a fini par mal gérer le reste. De son point de vu, il reste encore 0.009999999999998567 euro à rembourser. Moins qu'un centime. Et donc il augmente l'indice. Boum. Hors du domaine de validité.
Faire quelques tests pour vous persuader que les deux petites modifications vont suffire à faire fonctionner la fonction avec les centimes.
Float
L'encodage des floats est approximatifs dans la plupart des cas.
Il faut donc être très vigilant à leur propos.
>>> 0.3 == (3*0.1)
False
1
2
3
4
5
6 | |
Alors qu'on devrait afficher 0, c contient -5.948.10284 !
Comment faire alors pour traiter les cents ? Le plus "simple" est d'arrondir les calculs à chaque fois. Dans la solution que je vous propose, j'utilise la fonction native round qui permet d'arrondir au plus proche et en précisant le nombre de chiffres après la virgule à gérer. Ici, j'en place 2, par arrondir correctement au centime. 14.009999 euros va donc devenir 14.01 et nous éviterons le problème précédent.
17° Répondre aux deux questions suivantes qui traitent des erreurs d'exécution possibles.
1
2
3
4
5
6
7
8
9
10
11
12
13 | les_choix = [100, 50, 20, 10, 5, 2, 1, 0.50, 0.20, 0.10, 0.05, 0.01]
def rendre(a_rendre, choix=les_choix):
reponse = []
reste = round(a_rendre, 2)
i = 0
while reste > 0:
if reste >= choix[i]:
reste = round(reste - choix[i], 2)
reponse.append(choix[i])
else:
i = i + 1
return reponse
|
Tester la fonction avec deux trois valeurs pour vous persuader que cela fonctionne bien maintenant avec les centimes.
Une méthode plus propre consisterait plutôt à ne faire travailler la fonction qu'avec des cents. Comme cela, les calculs sont faits avec des entiers. Plus de problème de résultats approximatifs à cause de l'encodage des flottants.
0.1 euro est donc transformé en 10 cents.
5 euros est transformé en 500 cents...
✎ 18° Utiliser le programme puis répondre aux questions.
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | les_choix = [100, 50, 20, 10, 5, 2, 1, 0.50, 0.20, 0.10, 0.05, 0.01]
def rendre(a_rendre, choix=les_choix):
choix_en_cents = [round(valeur*100) for valeur in choix]
reponse = []
reste = round(a_rendre*100)
i = 0
while reste > 0:
if reste >= choix_en_cents[i]:
reste = reste - choix_en_cents[i]
reponse.append(choix[i])
else:
i = i + 1
return reponse
|
Question 1 : donner le contenu du tableau choix_en_cents après exécution de la ligne 4. Tenir compte du tableau fourni en ligne 1.
Question 2 : comment se nomme cette manière de créer un tableau : par compréhension, par extension et ajouts successifs, par omission, par dissimulation ?
Question 3 : les calculs des lignes 9 et 10 sont donc faits en cents. En regardant la ligne 10, dire si le résultat transmis par la fonction va lui être donné en euros ou en cents ?
Voilà pour le petit détour pour le problème des flottants. Comme vous le constatez, même avec un algorithme plutôt facile, il vaut toujours veiller aux calculs lorsqu'ils intégrent possiblement des nombres à virgules.
✎ 19° Ecrire la documentation de la fonction :
Vous noterez que j'ai rajouté ici une assertion pour provoquer une exception/erreur lorsqu'on demande de rembourser une somme négative. Pensez à en tenir compte lors de la rédaction de la documentation : la fonction n'accepte pas de valeurs négatives à rembourser.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | les_choix = [100, 50, 20, 10, 5, 2, 1, 0.50, 0.20, 0.10, 0.05, 0.01]
def rendre(a_rendre, choix=les_choix):
assert a_rendre > 0, "La somme à rendre doit être positive ou nulle à la limite"
choix_en_cents = [round(valeur*100) for valeur in choix]
reponse = []
reste = round(a_rendre*100)
i = 0
while reste > 0:
if reste >= choix_en_cents[i]:
reste = reste - choix_en_cents[i]
reponse.append(choix[i])
else:
i = i + 1
return reponse
|
Nous en avons fini avec cette présentation des algorithmes gloutons.
Stratégie gloutonne
La stratégie gloutonne est une stratégie de résolution de problèmes complexes, liée à l'optimisation d'une solution : il faut qu'il y ai plusieurs solutions possibles.
La stratégie gloutonne consiste à
On ne regarde pas au loin pour avoir une idée globale de la solution, chaque décision est prise en fonction des contraintes locales au moment du choix à faire.
Quelques exemples de problèmes et de solutions locales associées que nous avons vu :
7 - Greedy
En anglais, cette catégorie d'algorithmes se nommme greedy algorithm.
✎ 20° Chercher la traduction de greedy si vous ne connaissez pas. Expliquer en quoi cela correspond bien au fonctionnement d'un tel algorithme.
Expliquer alors en quoi Mr Greedy (qui préfère la malbouffe salée avant tout) à utiliser une méthode gloutonne (et donc locale) pour aboutir à ces choix (alors qu'en réalité, il préfère les hamburgers avant tout !)
8 - FAQ
Comment résoudre par force brute le voyageur de commerce de notre exemple ?
Voici une manière de faire qui ne nécessite pas trop de nouvelles notions. Je n'utilise que les choses que vous avez déjà vu jusqu'à présent. Bien entendu, nous pourrons faire bien plus court en terminale (en terme de lignes de codes et d'automatisation).
Le principe ici est de créer à chaque étape un tableau contenant les villes non encore visitées.
Pour cela, on génère un tableau contenant toutes les villes et on supprime les cases des villes déjà sélectionnées avec la méthode remove. Cette méthode permet de supprimer d'un tableau le premier élément ayant cette valeur. On décale alors tous les suivants d'une case à gauche pour combler le manque.
>>> legumes = ['Ananas', 'Bananes', 'Citrons', 'Dattes']
>>> fruits = ['Ananas', 'Bananes', 'Citrons', 'Dattes']
>>> fruits.remove('Bananes')
>>> fruits
['Ananas', 'Citrons', 'Dattes']
Voici un code possible qui n'utilise par la récursivité, qui nous simplifirait bien les choses mais que nous verrons en terminale.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55 | # Cette variable va contenir la plus petite distance trouvée par comparaison.
# Initialement j'y place donc une très grande valeur.
meilleur = 1E999
# Nous créons un dictionnaire les_villes qui va contenir des dictionnaires pour stocker les distances entre villes
brest = {'Bordeaux':598, 'Lille':708, 'Lyon':872, 'Marseille':1130, 'Paris':572}
bordeaux = {'Brest':598, 'Lille':802, 'Lyon':520, 'Marseille':637, 'Paris':572}
lille = {'Brest':708, 'Bordeaux':802, 'Lyon':650, 'Marseille':1002, 'Paris':225}
lyon = {'Brest':872, 'Bordeaux':520, 'Lille':650, 'Marseille':367, 'Paris':465}
marseille = {'Brest':1130, 'Bordeaux':637, 'Lille':1002, 'Lyon':367, 'Paris':777}
paris = {'Brest':572, 'Bordeaux':554, 'Lille':225, 'Lyon':465, 'Marseille':777}
les_villes = {'Brest':brest, 'Bordeaux':bordeaux, 'Lille':lille, 'Lyon':lyon, 'Marseille':marseille, 'Paris':paris}
# Nous créons un premier tableau qui va contenir les noms des villes
villes1 = [ville for ville in les_villes.keys()]
ville1 = villes1[0] # on choisit 'Brest' comme "point de départ" du chemin fermé
# On crée le second tableau contenant toutes les villes, sauf Brest.
villes2 = villes1.copy() # On copie le tableau précédent
villes2.remove(ville1) # on enlève le premier choix ('Brest')
for ville2 in villes2:
villes3 = villes2.copy() # On copie le tableau précédent
villes3.remove(ville2) # On enlève le choix qui vient d'être fait
for ville3 in villes3:
villes4 = villes3.copy() # On copie le tableau précédent
villes4.remove(ville3) # on enlève le choix de ville qui vient d'être fait
for ville4 in villes4:
villes5 = villes4.copy()
villes5.remove(ville4)
for ville5 in villes5:
villes6 = villes5.copy()
villes6.remove(ville5)
ville6 = villes6[0]
distance = les_villes[ville1][ville2] # distance entre ville 1 et 2
distance = distance + les_villes[ville2][ville3] # + distance entre ville 2 et 3
distance = distance + les_villes[ville3][ville4]
distance = distance + les_villes[ville4][ville5]
distance = distance + les_villes[ville5][ville6]
distance = distance + les_villes[ville6][ville1] # + distance pour repartir au départ
if distance < meilleur: # Si ce choix de villes est meilleur en terme de distance
meilleur = distance # On remplace meilleur par cette valeur
itineraire = f"{ville1}-{ville2}-{ville3}-{ville4}-{ville5}-{ville6}" # On crée un string contenant l'itinéraire qu'on vient de séléctionner pour le moment
# On affiche le résultat
print(f"{itineraire} en {meilleur} km")
|
Activité publiée le 16 05 2020
Dernière modification : 21 03 2021
Auteur : ows. h.