5 - Algorithmes gloutons
Nous allons voir aujourd'hui un nouveau type d'algorithme permettant de répondre à des problèmes complexes.
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. Il s'agit des problèmes dont la complexité est Non Polynomiale : elle est plus complexe.
Pour rappel
Différentes complexités
Voici un classement des types de complexité, de la catégorie la plus simple à la plus complexe.
Complexité 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.
Exemple vu cette année : renvoyer la valeur d'un élément d'un tableau. On calcule son adresse et on a va voir sur place.
Complexité logarithmique : Θ(log (n))
S'il s'agit d'un log en base 10, le temps de traitement d'un ensemble de 100 données est lié à log10(100) = log10(10*10) = log10(102) = 2.
S'il s'agit d'un log en base 10, le temps de traitement d'un ensemble de 1000 données est lié à log10(1000) = log10(10*10*10) = log10(103) = 3.
Exemple vu cette année : recherche par dichotomie. La complexité dans le pire des cas était en Θ(log2 (n)). Pour 1000 données, le temps d'exécution est lié à log2(1000) ≈ log2 (29.96) ≈ 9.96, donc environ 10.
Complexité racinaire : Θ(√(n))
Le temps de traitement d'un ensemble de 100 données est lié à √(100) = 10.
Le temps de traitement d'un ensemble de 1000 données est lié à √(1000) ≈ 32.
Complexité linéaire : Θ(n)
Le temps de traitement d'un ensemble de 100 données est lié à 100.
Le temps de traitement d'un ensemble de 1000 données est lié à 1000.
Exemple vu cette année : recherche séquentielle dans un tableau.
Complexité quasi-linéaire : Θ( n*log(n) )
Le temps de traitement d'un ensemble de 100 données est lié à 100*log2(100) soit 664.
Le temps de traitement d'un ensemble de 1000 données est lié à 1000*log2(1000) soit 9966.
Complexité polynomiale : Θ(nk)
Si on a du Θ(n2), on parle de complexité quadratique.
Le temps de traitement d'un ensemble de 100 données est lié à 1002 = 10 000.
Le temps de traitement d'un ensemble de 1000 données est lié à 1 000 000.
Et, c'est encore pire pour des valeurs de k de plus en plus grande : 10003, 10004...
Complexité exponentielle : Θ(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 it d'itinéraires différents de cette façon :
nt = 6*5*4*3*2*1
Il s'agit d'un calcul de factoriel.
On pourra donc noter nt = 6!
Et le résultat est nt = 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.
On calcule donc le nombre it d'itinéraires différentes de cette façon :
nt = 5*4*3*2*1
Il s'agit d'un calcul de factoriel.
On pourra donc noter nt = 5!
Dans la mesure, où nous avons n villes, la formule serait donc nt = (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.
Dans la mesure, où nous avons n villes, la formule serait donc nt = (n-1)! / 2
Pour n villes, on obtient du coup 60 parcours réellement différents. C'est mieux.
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 nt = (10-1)! / 2 avec Python :
>>> import math
>>> math.factorial(9) // 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.
Oui. Il n'empêche qu'ici la complexité est de type factorielle : Θ(n!). Et on ne peut pas y faire grand chose.
✎ 06° Combien de possibilités d'itinéaires différents va-t-on avoir pour 12 villes ? Juste deux petites villes en plus...
Rappel : nt = (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.
C'est faisable.
Je fournis dans la partie FAQ un programme qui permet de faire cela. Il est long et répétitif car il vous manque encore quelques notions en informatique pour le rendre plus compact.
Il n'en reste pas moins qu'il faut faire les 60 calculs pour 6 villes mais 20 millions de calculs pour 12 villes !
Le plus petit trajet 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
Par rapport au premier itinéraire fait au hasard ou presque, on voit donc qu'il vaut mieux faire Brest-Lille que Brest-Paris.
✎ 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 résultat 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
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. S'il n'y a qu'une solution UNIQUE, ce n'est pas de l'optimisation !
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 aux choix suivants :
- Si la case actuelle est plus haute que les cases juste à droite et juste à gauche : on stoppe. On considère qu'il s'agit du point le plus haut.
- Sinon, on se dirige vers la case qui grimpe le plus.
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 au 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.
Le fondement de ces algorithmes est donc de créer une solution au problème global en répondant successivement à des sous-problèmes locaux : on espère que répondre de façon optimale localement va mener au final à une réponse globale au moins "correcte".
On dit que l'algorithme glouton fournit une heuristique : une méthode fournissant rapidement une solution non nécessairement optimale pour un problème d'optimisation. On les utilise donc surtout sur les problèmes NP, pour lesquels la résolution mathématique et la résolution par force brute ne sont pas possibles.
Les algorithmes gloutons ne peuvent donc pas garantir que la solution proposée soit une solution optimale. On fournit juste une solution au problème.
Et voilà comment on fait : on triche. On ne peut pas fournir LA réponse (car ça demande trop de temps de calcul). Donc, on s'arrange pour fournir une solution
- en se basant sur des décisions optimales localement,
- en espérant qu'au final la solution globale trouvée ne soit pas trop mauvaise.
Appliquons cela à notre voyageur de commerce.
Voici la solution locale optimale que nous allons toujours privilégier : 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...
Nous pourrions affiner notre solution optimale localement : on pourrait choisir par exemple d'estimer la plus courte distance pour parcourir deux villes depuis le point actuel, ou encore d'autres choses. Il y a souvent plusieurs façons de faire.
Je répète : le point commun à toutes ces méthodes gloutonnes est qu'on applique localement toujours la même façon de faire en espérant que cela mène à une solution globale correcte.
5 - Rendu de monnaie
Autre problème typique : 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 condition : 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 cette solution locale optimale : 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 les_choix regroupant les sommes qu'on peut rendre et une fonction rendre qui récupère la somme à rendre dans le paramètre a_rendre et le tableau des billets et pièces disponible dans le paramètre choix.
Cette fonction devra renvoyer un tableau contenant les éléments à rendre. Par exemple [100, 10, 5, 2, 2] pour rendre 119 euros.
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
index ← 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[index]
on peut rendre une partie de l'argent avec le billet ou la pièce choix[index]
reste ← reste - choix[index]
on rajoute choix[index] dans reponse
SINON
choix[index] est plus grand que la somme à rendre, il faut passer au billet ou la pièce suivante
index ← index + 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
index = 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
index = 0
while reste > 0 :
if reste >= choix[index] :
reste = reste - choix[index]
reponse.append(choix[index])
else :
index = index + 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'index 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'index et va finir par demander un index incorrect. La boucle TANT QUE ne s'arrêterait pas sinon. Il reste toujours 50 cents à rendre. C'est l'erreur d'index 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[index] :
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'index. 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)
index = 0
while reste > 0 :
if reste >= choix[index] :
reste = round(reste - choix[index], 2)
reponse.append(choix[index])
else :
index = index + 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)
index = 0
while reste > 0 :
if reste >= choix_en_cents[index] :
reste = reste - choix_en_cents[index]
reponse.append(choix[index])
else :
index = index + 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)
index = 0
while reste > 0 :
if reste >= choix_en_cents[index] :
reste = reste - choix_en_cents[index]
reponse.append(choix[index])
else :
index = index + 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.