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.
La force brute : image tirée du film HULK
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 a 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.
La stratégie gloutonne : Mr Glouton préfère la malbouffe salée, puis la malbouffe sucrée et les crudités s'il n'a vraiment pas le choix
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)
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 meilleure 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.
(Rappel).1 - Introduction à la notion de coût d'un algorithme
Définition
Le coût d'un algorithme exprime la façon dont l'algorithme réagit globalement à l'augmentation du nombre n de données à traiter.
On évalue souvent le coût dans le pire des cas car il borne le comportement de l'algorithme : s'il se comporte bien dans le pire des cas, c'est qu'à priori nous allons pouvoir l'utiliser.
PROBLEMES FACILES
Facile veut dire qu'on peut utiliser un programme qui fournira la réponse en un temps raisonnable.
Coût constant (noté 1 ou CST)
Si n*2 alors op inchangé
Si on modifie le nombre n de données, le nombre d'opérations élémentaires op reste le même.
Exemple
Avec n = 6 données, on a besoin de op = 5 opérations élémentaires.
Si n*2 (n = 12), alors op = 5.
Si n*4 (n = 24), alors op = 5.
Si n*8 (n = 48), alors op = 5.
C'est donc pas mal !
Les coûts logarithmiques (notés logk(n)
si n*k alors op+1
Si on multiple par k le nombre n de données, alors on augmente juste op de 1.
Plus k est grand, plus l'algorithme va être rapide. Quelques exemples où le coût devient de moins en moins bon :
log10 : n*10 alors op+1. Celui-ci est souvent utilisé en physique-chimie.
log3 : n*3 alors op+1
loge ou juste ln : n*e alors op+1. e est la constante de Néper qui vaut approximativement 2,71. Ce logarithme particulier se nomme d'ailleurs le logarithme népérien.
log2 ou juste lg : n*2 alors op+1. C'est celui qu'on rencontre le plus souvent en informatique.
dont le coût logarithmique base 2 (noté log2(n) ou lg(n) )
si n*2 alors op+1
Si on multiple par 2 le nombre n de données, alors on augmente juste op de 1.
De façon plus détaillée,
si n est multiplié par 2, alors on augmente juste op de 1;
si n est multiplié par 4, alors on augmente juste op de 2;
si n est multiplié par 8, alors on augmente juste op de 3;
...
Exemple
Avec n=6 données, on a besoin de op=5 opérations élémentaires.
Si n*2 (12 données), on aura op+1 soit 5+1=6 opérations.
Si n*4 (24 données), on aura op+2 soit 5+2=7 opérations.
Si n*8 (48 données), on aura op+3 soit 5+3=8 opérations.
Ce coût se situe donc entre CONSTANT et LINEAIRE.
Les coûts polynomiaux (notés nk)
Si n*2 alors op*constante (on notera que la constance vaut 2k)
Si on multiple par 2 le nombre n de données, on multiple par la constante 2k le nombre op d'opérations élémentaires.
Plus k est grand, plus l'algorithme va être lent. Quelques exemples où le coût devient de moins en moins bon :
n1 : n*2 alors op*2 : le coût linéaire.
n2 : n*2 alors op*22 : le coût quadratique.
n3 : n*2 alors op*23 : le coût cubique.
dont le coût linéaire (noté n)
Si n*2 alors op*2
Si on double le nombre n de données, on double le nombre op d'opérations élémentaires.
De façon plus mathématique,
si n est multiplié par 2, alors on multiple op par 2;
si n est multiplié par 3, alors on multiple op par 3;
si n est multiplié par 4, alors on multiple op par 4
...
Exemple
Avec n=6 données, on a besoin de op=5 opérations élémentaires.
Si n*2 (12 données), on aura op*2 soit 5*2=10 opérations.
Si n*4 (24 données), on aura op*4 soit 5*4=20 opérations.
Si n*8 (48 données), on aura op*8 soit 5*8=40 opérations.
C'est un peu plus long que du coût constant.
dont le coût quadratique (noté n2)
Si n*2 alors op*(22)
Si on double le nombre n de données, on quadruple le nombre op d'opérations élémentaires.
De façon plus mathématique,
si n est multiplié par 2, alors on multiple op par 22;
si n est multiplié par 3, alors on multiple op par 32;
si n est multiplié par 4, alors on multiple op par 42
...
Exemple
Avec n=6 données, on a besoin de op=5 opérations élémentaires.
Si n*2 (12 données), on aura op*22 soit 5*4=20 opérations.
Si n*4 (24 données), on aura op*42 soit 5*16=80 opérations.
Si n*8 (48 données), on aura op*82 soit 5*64=320 opérations.
Cela devient réellement de plus en plus grand lorsque les données deviennent importantes.
et tous les autres coûts polynomiaux (notés nk)
Si n*2 alors op*(2k)
Si on double le nombre n de données, on multiplie par la constante 2k le nombre op d'opérations élémentaires.
De façon plus mathématique,
si n est multiplié par 2, alors on multiple op par 2k;
si n est multiplié par 3, alors on multiple op par 3k;
si n est multiplié par 4, alors on multiple op par 4k
...
PROBLEMES DIFFICILES
Difficile veut dire qu'on peut utiliser un programme mais qu'il fournira la réponse en un temps déraisonnable lorsque le nombre de données n deviendra grand.
Coût exponentiel (noté kn)
Si n*2 alors op*(kn), ou encore si n+1 alors op*k
Si on double le nombre n de données, on multiplie par kn le nombre op d'opérations élémentaires. Notez bien que le facteur multiplicatif n'est donc plus une constante par rapport à n.
Cela veut également dire que si on augmente juste de 1 le nombre n de données, on multiplie par k le nombre op d'opérations élémentaires.
Plus k est grand, plus l'algorithme va être lent.. Quelque exemples où le coût devient de moins en moins bon :
2n : n+1 alors op*2. L'exponentielle base 2 est rencontrée assez souvent en informatique.
en : n+1 alors op*e. e est la constante de Néper qui vaut approximativement 2,71. Cette fonction exponentielle particulière se nomme juste "fonction exponentielle".
3n : n+1 alors le op*3. L'exponentielle base 3.
10n : n+1 alors le op*10. L'exponentielle base 10.
dont l'exponentielle base 2 (noté 2n)
Si n*2 alors op*(2n), ou encore si n+1 alors op*2
Si on double le nombre n de données, on multiplie par 2n le nombre op d'opérations élémentaires. Notez bien que le facteur multiplicatif n'est donc plus une constante par rapport à n.
Cela veut également dire que si on augmente juste de 1 le nombre n de données, on multiplie par 2 le nombre op d'opérations élémentaires.
Exemple 1 où on augmente les données de 1 à la fois
Avec n=1 données, on a besoin de op=5 opérations élémentaires.
Si on passe de 1 à 2 données (n+1 avec n=1), on aura op*2 soit 5*2=10 opérations.
Si on passe de 2 à 3 données (n+1 avec n=2), on aura op*2 soit 10*2=20 opérations.
Si on passe de 3 à 4 données (n+1 avec n=3), on aura op*2 soit 20*2=40 opérations.
Si on passe de 4 à 5 données (n+1 avec n=4), on aura op*2 soit 40*2=80 opérations.
Exemple 2 où on double les données :
Avec n=6 données, on a besoin de op=5 opérations élémentaires.
Si on passe de 6 à 12 données (n*2 avec n=6), on aura op*2n soit 5*26=5*64=320 opérations.
Si on passe de 12 à 24 données (n*2 avec n=12), on aura op*2n soit 320*212=320*4096=1310720 opérations.
On voit bien qu'avec une évolution exponentielle (même base 2, la moins "grave"), on perd rapidement la possibilité de réaliser tous les calculs nécessaires :
Si n*2 alors plus que op*((n+1)n) opérations car op dépend de n!= n*(n-1)*(n-2)*...*3*2*1.
Par définition, la factorielle de n vaut n*(n-1)*(n-2)*...*3*2*1.
Lorsqu'on double le nombre de données, on passe donc de n! à (2n)!.
Cela veut dire qu'on prend le nombre d'opérations nécessaires pour n! et qu'on les multiplie par (n+1)*(n+2)*(n+3)*...*(n+n).
On a donc n multiciplication à faire par des facteurs qui sont tous plus grand que n.
On doit donc multiplier le nombre d'opérations par un facteur plus grand que nn. C'est donc encore pire que le coût exponentiel.
Exemple
Avec n = 1 donnée, n! = 1 = 1.
Avec 2, n! = 1*2 = 2.
Avec 3, n! = 1*2*3 = 6.
Avec 4, n! = 1*2*3*4 = 24.
Avec 5, n! = 1*2*3*4*5 = 120.
Avec 6, n! = 1*2*3*4*5*6 = 720.
Avec 7, n! = 1*2*3*4*5*6*7 = 5040.
Avec 8, n! = 1*2*3*4*5*6*7*8 = 40320.
On pourrait croire que cela évolue moins vite que l'exponentiel mais dès que n devient grand, cela explose encore plus vite que le coût exponentiel.
>>> import math
>>> math.factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000>>> math.factorial(1000)
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
PROBLEMES INDECIDABLES
Notez bien que les problèmes faciles et difficiles sont décidables (le programme finira toujours par fournir une réponse si on lui laisse le temps).
Il existe des problèmes encore plus complexes :: les problèmes indécidables. Sur ces problèmes, l'ordinateur répond parfois mais par sur une infinité de calculs sur d'autres entrées. Et dans ce cas, il ne pourra jamais vous répondre.
Sur les deux derniers cas, l'ordinateur va travailler 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.
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éraires 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.
2 Calcul d'une factorielle
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éraires différents va-t-on avoir pour 12 villes ? Juste deux petites villes en plus...
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 celui proposé ici donne un trajet optimal (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.
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.
4 Principe des algorithmes gloutons
Principe de la stratégie
On résout 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.
Pour pouvoir utiliser un algorithme glouton, il faut que le problème possède 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 (voir le programme de Terminale).
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.
Heuristique
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...
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 choisissant 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 choisissant 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.
Nous allons finir en appliquant la stratégie gloutonne du rendu de monnaie à Python.
On commencera par créer un tableau les_choix, trié en ordre décroissant et regroupant les pièces/billets 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 :
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 globale les_choix. Mais on peut la faire travailler avec un autre tableau.
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 :
6.1 - 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é
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 QUEreste est strictement supérieure 0
SIreste 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
Renvoyerreponse
15-A° Utiliser dans Thonny les instructions suivantes pour comprendre comment rajouter une case dans un tableau Python : le type list n'est pas un tableau statique (nombre de cases fixe) mais un tableau dynamique (nombre de cases variables).
Vous trouverez ci-dessous quelques indications vous permettant d'avancer.
Rappel : pour rajouter à élément à un tableau, il faut utiliser la méthode append.
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) :
En apparence, puisque la condition du TANT QUE est une condition du type whileun>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.
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.
6.2 - Floats
L'encodage des floats est approximatif dans la plupart des cas.
JAMAIS DE TEST D'EGALITE ENTRE DEUX FLOAT !
>>> 0.3 == (3*0.1)
False
VIGILANCE SUR LES CALCULS REPETIFS
1
2
3
4
5
6
a=0.1b=0.3c=b-3*afordinrange(1000):c=c*2print(c)
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, pour arrondir correctement au centime près. 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.
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.
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 :
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.
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]defrendre(a_rendre,choix=les_choix):asserta_rendre>0,"La somme à rendre doit être positive ou nulle à la limite"choix_en_cents=[round(valeur*100)forvaleurinchoix]reponse=[]reste=round(a_rendre*100)i=0whilereste>0:ifreste>=choix_en_cents[i]:reste=reste-choix_en_cents[i]reponse.append(choix[i])else:i=i+1returnreponse
Nous en avons fini avec cette présentation des algorithmes gloutons.
6.3 - Conclusion 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 à
faire des choix locaux qu'on pense efficaces
pour résoudre le problème au niveau global.
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 :
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
En anglais, cette catégorie d'algorithmes se nomme 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 !)
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.
# 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 villesbrest={'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 villesvilles1=[villeforvilleinles_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édentvilles2.remove(ville1)# on enlève le premier choix ('Brest')forville2invilles2:villes3=villes2.copy()# On copie le tableau précédentvilles3.remove(ville2)# On enlève le choix qui vient d'être faitforville3invilles3:villes4=villes3.copy()# On copie le tableau précédentvilles4.remove(ville3)# on enlève le choix de ville qui vient d'être faitforville4invilles4:villes5=villes4.copy()villes5.remove(ville4)forville5invilles5:villes6=villes5.copy()villes6.remove(ville5)ville6=villes6[0]distance=les_villes[ville1][ville2]# distance entre ville 1 et 2distance=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épartifdistance<meilleur:# Si ce choix de villes est meilleur en terme de distancemeilleur=distance# On remplace meilleur par cette valeuritineraire=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ésultatprint(f"{itineraire} en {meilleur} km")
Activité publiée le 16 05 2020
Dernière modification : 13 04 2024
Auteur : ows. h.
