Algo Gloutons

Identification

Infoforall

9 - Algorithmes gloutons


Nous avons vu un premier algorithme de type décisionnel avec l'algorithme des k plus proches voisins.

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 : tri par insertion

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é 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.

France

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.

France

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

France

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.

Recherche du point maximum

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.

Recherche du point maximum - deux

Que faire ?

Ca grimpe à gauche et pas à droite : on part à droite. Nous arrivons au point 3.

Recherche du point maximum - troisième décision

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.

Recherche du point maximum - quatrième décision

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.

Recherche du point maximum

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.

Recherche du point maximum Recherche du point maximum

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 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.

Forcément, c'est moins bien que la solution optimale de 3000 km. Avec plus de villes que sur notre exemple, le programme en force brute tournerait encore pour 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 toujours d'abord de 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 avec un ensemble de pièces de 5 euros, deux euros et un euro. 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 un ensemble de pièces de 8 euros, 5 euros, et un euro. 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 donne ne donne pas toujours la solution optimale. Mais ça fonctionne plutôt bien. Et 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 qui est situé derrière le signe égal.

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'implantation): 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

    restea_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]

        restereste - 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

        indexindex + 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 deux questions suivantes qui traitent des erreurs d'exécution possibles.

Question 2 : 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 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.

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, 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, explications sur les préconditions (sur les paramètres d'entrée), explication sur la ou les post-conditions (sur la réponse) et 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 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.

Retenez donc qu'il s'agit d'une manière de résoudre les problèmes complexes liés à l'optimistion d'une solution.

Ils consistent à faire des choix locaux qu'on pense efficaces pour résoudre le problème 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

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.

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")

La stratégie gloutonne n'est qu'une technique parmi d'autres.

Ceux qui continuent NSI verront d'autres techniques de résolution de problèmes en terminale.

Activité publiée le 16 05 2020
Dernière modification : 16 05 2020
Auteur : ows. h.