CHAPITRE 1 : LE RÉFLEXE DU MARCHÉ

Au marché Mokolo, à Yaoundé, Mama Ngono vend des beignets-haricot. Quand une cliente lui tend un billet de 2 000 FCFA pour 150 FCFA de beignets, elle rend la monnaie en deux secondes, sans réfléchir. Elle vient d'exécuter un algorithme glouton.

Ce qu'elle fait sans y penser

Mama Ngono doit rendre 1 850 FCFA. Elle ne se demande pas quelle est la meilleure combinaison possible. Elle fait ceci :

• Quelle est la plus grosse coupure que je peux donner ? Un billet de 1 000. Elle le sort. Il reste 850.
• Et maintenant ? Un billet de 500. Il reste 350.
• Une pièce de 100. Il reste 250. Encore 100. Il reste 150. Encore 100. Il reste 50.
• Une pièce de 50. Il ne reste rien.

Six coupures, et c'est réglé. À aucun moment elle n'a comparé des combinaisons. À aucun moment elle n'est revenue sur un choix déjà fait.

Un algorithme glouton prend, à chaque étape, le meilleur choix du moment, puis il passe au suivant sans jamais se retourner.

La définition

Un second exemple, encore plus simple

Awa, étudiante à Ngoa-Ekellé, doit former le plus grand nombre possible avec les chiffres 2, 9, 7, 4, 8, 1, chacun utilisé une seule fois.

Elle ne teste pas les 720 arrangements possibles. Elle se dit : le chiffre le plus à gauche est celui qui pèse le plus lourd, donc j'y mets le plus grand chiffre disponible. Puis le suivant. Et ainsi de suite.

chiffres disponibles : 2 9 7 4 8 1

je prends 9  ->  9              il reste 2 7 4 8 1
je prends 8  ->  98             il reste 2 7 4 1
je prends 7  ->  987            il reste 2 4 1
je prends 4  ->  9874           il reste 2 1
je prends 2  ->  98742          il reste 1
je prends 1  ->  987421         il ne reste rien

Résultat : 987421. Et ici, c'est bel et bien le plus grand nombre possible. Le glouton a trouvé l'optimum.

Pourquoi on s'en sert

Parce que l'autre méthode, essayer toutes les possibilités, devient vite impraticable.

Cinquante objets, c'est peu. Et pourtant, un million de milliards de combinaisons : aucune machine n'en viendra à bout. Le glouton, lui, traite ces cinquante objets en cinquante étapes.

Le squelette, toujours le même

Tous les algorithmes gloutons se ressemblent. Voici leur forme générale :

fonction GLOUTON(candidats)
    solution <- ensemble vide

    tant que la solution n'est pas complete
          et qu'il reste des candidats faire

        x <- le candidat le plus prometteur      // le choix glouton
        retirer x des candidats

        si ajouter x garde la solution realisable alors
            ajouter x a la solution
        fin si

    fin tant que

    retourner solution
fin fonction

Tout tient dans une seule ligne : le candidat le plus prometteur. C'est le critère glouton, et c'est lui qu'il faut trouver pour chaque problème. Le plus gros billet ? Le plus grand chiffre ? Le plus rentable au kilo ? Celui qui finit le plus tôt ? Tout le travail est là.

L'avertissement

Il faut le dire tout de suite, parce que c'est le cœur du sujet :

Un algorithme glouton ne donne pas toujours la meilleure solution.

Parfois il la donne, c'est le cas de la monnaie de Mama Ngono, et nous le démontrerons. Parfois il passe à côté : nous verrons Tonton Émile y perdre 10 000 FCFA au chapitre 3.

Tout l'intérêt du cours est là : savoir reconnaître dans quel cas on se trouve.

chiffres : 5 0 3 8 1

le plus petit : 0  ->  0
puis          : 1  ->  01
puis          : 3  ->  013
puis          : 5  ->  0135
puis          : 8  ->  01358

20 -> 30 objets : 10 de plus -> 2^10 = 1 024 fois plus
                  1 024 secondes = 17 minutes

20 -> 40 objets : 20 de plus -> 2^20 = 1 048 576 fois plus
                  1 048 576 secondes = 12 jours