Méthodes par dichotomie

et algorithmes gloutons

Objectifs
A la fin de la séquence d’enseignement les élèves doivent :
• pouvoir citer les avantages à adopter une approche par dichotomie en comparaison avec une approche
linéaire
• reconnaitre un cas où une approche par dichotomie est envisageable
• savoir coder en Python un algorithme de recherche dichotomique dans un tableau trié
• avoir quelques notions de coûts linéaire et logarithmique
• distinguer un choix optimal global d’un choix localement optimal
• savoir ce qu’est un algorithme glouton
• savoir coder en Python quelques exemples classiques d’algorithmes gloutons

Table des matières

1 Algorithmes dichotomiques 2
1.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Exemples classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Recherche dichotomique d’une valeur dans un tableau trié . . . . . . . . . . . . . . . . . . 2
1.2.2 Exponentiation rapide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Algorithmes gloutons 3
2.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Exemples classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2.1 Le voyageur de commerce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2.2 Rendu de la monnaie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.3 Sac à dos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2.4 Autres exemples classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Lycée Carnot - Dijon MPSI & PCSI - Algorithmes I Germain Gondor

1. Algorithmes dichotomiques 2/6

1 Algorithmes dichotomiques

1.1 Principe

Il est des situations où un problème de dimension n se trouve réduit à un problème de dimension n//2 à l’itération
suivante.

Exemple : trouver un nombre entre 0 et 100 choisi par un opérateur (pas forcément
5
humain) qui indique si la proposition est plus grande ou plus petite que la solution.
2 8
Tester les valeurs par ordre croissant peut conduire à 101 propositions. . . . Avec une
méthode par dichotomie, le nombre d’itérations est au maximum 7. 0 3 6 9

Ci-contre, arbre d’appel pour une valeur comprise entre 0 et 10. 1 4 7 10

Le principe est donc de diviser le problème en deux sous problèmes. On parle alors de méthode par dichotomie.
Elle fait partie des stratégie de type diviser pour mieux régner.

L’étude de la complexité au second semestre montrera qu’une telle méthode à un coût en log(n) quand une ap-
proche naı̈ve à un coût en n (coût linéaire).

1.2 Exemples classiques

1.2.1 Recherche dichotomique d’une valeur dans un tableau trié

Enoncé : Recherche dichotomique (ou binary seach) d’une valeur dans un tableau de valeurs trié
Écrire une fonction recherche dicho(T, x) qui prend en argument un tableau trié T de flottants et x
un flottant. La fonction renvoie un indice de x si x est une des valeurs du tableau et -1 sinon.
Principe :
Prendre une valeur au milieu du tableau. Si c’est la valeur recherchée, c’est gagné, sinon on la compare à la
valeur recherchée et on prendre la moité du tableau où est potentiellement la valeur recherchée.

Algorithm 1 Recherche dichotomique dans un tableau trié

entrée: T un tableau de n valeurs et 4: tant que min<max et T[mil],x faire 12: si T[mil],x alors
x un élément (pas forcément du ta- 5: si T[mil]<x alors 13: rep ← -1
bleau) 6: min← mil+1 14: sinon
résultat: -1 si x < T, l’indice d’un x 7: sinon 15: rep ← mil
dans le tableau T sinon 8: max ← mil-1 16: fin si
1: recherche dicho(T, x) 9: fin si 17: renvoi: rep
2: n← taille(T ) 10: mil← (min+max)//2
3: min,max,mil← 0,n-1,(min+max)//2 11: fin tant que

1.2.2 Exponentiation rapide

Enoncé : Exponentiation rapide

Écrire une fonction puiss(x, n) qui prend en argument un flottant x et un entier n et qui renvoie xn .
Exemple : pour calculer x5 , on calcule x2 puis x4 et finalement x5 .

Lycée Carnot - Dijon MPSI & PCSI - Algorithmes I Méthodes par dichotomie
et algorithmes gloutons
2. Algorithmes gloutons 3/6

Principe :
Se servir des résultats intermédiaires pour accélérer
Algorithm 2 Exponentiation rapide itérative le processus de calcul de xn en décomposant n en
entrée: x un nombre réel et n un entier naturel puissance de 2.
résultat: un nombre réel r = xn
puiss(x, n) Algorithm 3 Exponentiation rapide récursive
1: si n==0 alors entrée: n un entier positif et x un nombre réel
2: renvoi: 1 résultat: un nombre réel r = xn
3: fin si puis rec(x, n)
4: r← 1 1: si n==0 alors
5: tant que n > 0 faire 2: renvoi: 1
6: si n modulo 2==1 alors 3: sinon
7: r←r.x 4: si n modulo 2==0 alors
8: fin si 5: renvoi: puis rec(x.x,n/2)
9: x←x.x 6: sinon
10: n←n//2 7: renvoi: [Link] rec(x.x,(n-1)/2)
11: fin tant que 8: fin si
12: renvoi: r 9: fin si

2 Algorithmes gloutons

2.1 Principe

Il est des situations où un problème de dimension n se trouve très long à résoudre à cause du nombre de cas
d’étude requis (par exemple n!). Si n = 20 et que la résolution avec une méthode par force brute nécessite l’étude
de n! cas, le temps de calcul va être très très long.

Exemple : un régisseur doit éclairer la salle des fêtes avec n spots suspendus au faux-plafond. Chaque spot est
doté d’une entrée et d’une sortie électrique afin de les brancher en série.
Comme la salle n’a qu’un tableau électrique et pas de multiprises, il se demande comment utiliser le moins de
câble possible pour relier tous les spots les uns à la suite des autres.
3!
Avec 3 spots, il a déjà A33 = = 6 cas possibles : [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2] et [3, 2, 1].
(3 − 3)!
Le principe devient alors de ne plus rechercher la solution optimale mais prendre, à chaque itération, la solu-
tion locale optimale. Un algorithme glouton (en anglais greedy algorithm) recherche à chaque itération, parmi les
choix qui se présentent, celui qui sera localement optimal, sans remettre en cause les choix précédents et sans se
soucier de ce qu’il adviendra ensuite.

Remarque : Hélas, une succession de choix localement optimaux ne donne pas forcément une solution optimale.

2.2 Exemples classiques

2.2.1 Le voyageur de commerce

Enoncé : Problème du voyageur de commerce

Trouver le plus court chemin pour qu’un voyageur de commerce puisse passer exactement une fois chez ses
clients et rentrer chez lui.

Lycée Carnot - Dijon MPSI & PCSI - Algorithmes I Méthodes par dichotomie
et algorithmes gloutons
2. Algorithmes gloutons 4/6

b b
d h h d h

f
e a = 12 km a = 12 km
c b = 16 km c d = 5 km

a
a
a

g
g

h ≈ 12,36 km h ≈ 12,36 km
g ≈ 9,84 km c = 20 km
total ≈ 50,22 km total ≈ 49,34 km

Enoncé : Plus court chemin passant par tous les points

Écrire une fonction trajet(L, dep) prenant en argument une liste L de tuples contenant les coor-
données cartésiennes de points ainsi que dep l’indice du point de départ et renvoyant une liste des indices
de L permettant, à partir du premier tuple, d’obtenir la plus petite longueur de courbe passant par tous les
points une et une seul fois avant de revenir au point initial.
Principe :
On part du part du premier point, on calcule toutes les distances vers les autres points. On prend le plus
proche et on recommence en calculant les distances vers les points encore disponibles, jusqu’à ce qu’il n’y ait
plus de points disponibles.

Algorithm 4 Voyageur de commerce

entrée: L une liste de coordonnées cartésiennes 11: pour k = j+1 à n faire

résultat: une liste d’indices correspondant au par- 12: si dispo[k] alors
cours des éléments de L minimisant le chemin 13: d ←distance(L[pos], L[k])
trajet(L, dep) 14: si d min > d alors
1: n, pos ←taille(L), dep 15: d min ←d
2: dispo ←[Vrai]*n 16: plus proche ←k
3: parcours ←[dep] 17: fin si
4: pour i = 1 à n-1 faire 18: fin si
5: j ←0 19: fin pour
6: tant que non dispo[j] faire 20: pos ←plus proche
7: j ←j + 1 21: dispo[pos] ←Faux
8: fin tant que 22: [Link](pos)
9: d min ←distance(L[pos], L[j]) 23: fin pour
10: plus proche ←j 24: renvoi: parcours

2.2.2 Rendu de la monnaie

Enoncé : Rendu de la monnaie

Étant donnée une monnaie avec sa déclinaison en pièces et billets de différentes valeurs, l’objectif du banquier
pressé est de donner au client la somme désirée en prenant le moins d’éléments.
En euros, la plus petite division est la pièce de 1 centime. A la pompe à essence, il est donc nécessaire d’arrondir
le prix au centième d’euros près ; il est impossible de détailler au millième.

On considère donc un n-uplet des valeurs prises par les différents supports de la monnaie et on considère que
chacun des supports est infiniment disponible.

Enoncé : Moindre nombre de pièces

Écrire une fonction merci(L, som) qui prend en argument une liste L contenant par ordre décroissant
les valeurs des supports de la monnaie et un flottant som correspondant au montant à rendre. La fonction
renvoie une liste dont le ième élément correspond au nombre de supports de valeur L[i] utilisés pour
obtenir le montant à rendre.

Lycée Carnot - Dijon MPSI & PCSI - Algorithmes I Méthodes par dichotomie
et algorithmes gloutons
2. Algorithmes gloutons 5/6

Pour rendre 8 centimes, par exemple, en se limitants aux pièces de 5, 2 et 1 centimes, on a les combinaisons
suivantes : [1, 1, 1], [1, 0, 3], [0, 4, 0], [0, 3, 2], [0, 2, 4], [0, 1, 6], [0, 0, 8]. On préfère bien sûr la première solution
qui requière simplement 3 pièces.

Pour rendre le montant de 26,92 e, le nombre de

Algorithm 5 Rendu de la monnaie
combinaisons est bien plus grand en utilisant les
entrée: L une liste des valeurs des différents supports
billets de 20, 10 et 5 euros, les pièces de 2 et 1
de la monnaie, triés par ordre décroissant et som le
euros et les pièces de 50, 20, 10, 5, 2 et 1 centimes
montant à rendre
d’euros.
résultat: support une liste des nombres de supports
utilisés par valeur
Principe :
merci(L, som)
Il s’agit d’utiliser en premier lieu les plus gros
1: i, support ←0, []
supports puis compléter avec les plus petits.
2: tant que i < taille(L) faire
Remarque : Il existe un support unitaire (pièce de 3: ni ←entier(som / L[i])
1 centime) pour la plus petite valeur payable en 4: som ←som - ni*L[i]
euros. L’algorithme glouton donnera ici la solution 5: [Link](ni)
exacte et optimale dans le cas où chaque pièce et 6: i ←i + 1
chaque billet est infiniment disponible. 7: fin tant que
8: renvoi: support

Cependant, avec d’autres monnaies, le choix des coupures (ou support de la monnaie) peut conduire un algo-
rithme glouton à ne pas trouver la solution optimale. Exemple : le système de monnaie anglais avant 1960.

On peut maintenant se placer dans un cas où on dispose d’un porte monnaie fini. Il contient un ensemble de
pièces.

On peut alors utiliser un algorithme glouton >>> merci([50, 20, 10, 5, 5, 2, 2, 2, 2], 21)
permettant de déterminer quelles pièces choisir ([20], 1)
pour rendre la monnaie avec le moins de pièces >>> merci([50, 10, 5, 5, 2, 2, 2, 2], 21)
possible (ou le plus de pièces possible). Hélas, ([10, 5, 5], 1)
un algorithme glouton peut ne pas trouver de >>> merci([50, 10, 5, 2, 2, 2, 2], 21)
solution bien qu’une au moins existe. ([10, 5, 2, 2, 2], 0)

2.2.3 Sac à dos

Enoncé : Problème du sac à dos

Comment choisir quels objets placer dans un sac à dos limité au niveau du poids total ? Chaque objet a une
masse et une valeur données. Comment emporter la plus grande quantité de valeurs possible dans le sac ?
En fonction du nombre d’objets, il peut exister un grand nombre de combinaisons possibles. Pour ne pas toutes
les tester, un algorithme glouton peut être utilisé. Cependant, à chaque itération, faut-il privilégier la valeur
maximale, la masse minimale, le meilleur rapport valeur/masse ?

Enoncé : Optimisation du choix de valeurs pondérées

Écrire une fonction selection(L, crit, m max) qui prend en argument un n-uplet L (ou une liste)
de 2-uplet de flottants qui représentent respectivement la valeur et la masse d’un objet. La fonction prend
également deux autres arguments : crit, un entier permettant de choisir la stratégie de sélection (0 pour la
valeur, 1 pour l’inverse de la masse, 2 pour le rapport valeur/masse) et m max, la masse à ne pas dépasser. La
fonction renvoie la liste des objets sélectionnés pour maximiser la valeur emportée en fonction de la stratégie
adoptée.

Lycée Carnot - Dijon MPSI & PCSI - Algorithmes I Méthodes par dichotomie
et algorithmes gloutons
2. Algorithmes gloutons 6/6

Principe :
Trier les objets en fonction du critère de sélection : par ordre décroissant pour la valeur et le ratio valeur/-
masse ; par ordre croissant pour la masse. Parcourir la liste des objets triés et prendre l’objet si la masse
accumulée en le prenant ne dépasse pas la masse totale autorisée.
Remarque : le critère d’optimisation influe sur le résultat en fonction des objets de départ.

Exemple : avec 7 objets : (4, 10), (2, 2), (2, 1), (1, 1), (10, 4) et (7, 6)

Critère valeur maximale : Critère masse minimale : Critère ratio valeur/masse maximal :

(10, 4), (7, 6), (2, 2) (2, 1), (1, 1), (2, 2), (10, 4) (10, 4), (2, 1), (7, 6), (1, 1)

Valeur emportée : 19 Valeur emportée : 15 Valeur emportée : 20

Masse totale : 12 Masse totale : 8 Masse totale : 12
Avec un autre choix d’objets, le critère de valeur maximale peut conduire à un meilleur résultat que le critère de
ratio valeur/masse maximal.

Algorithm 6 Sac à dos

entrée: L une liste de 3-uplets triée par ordre décroissant sur une des trois colonnes et mmax un flottant
représentant la masse maximale admissible
résultat: choix, val, m avec choix la liste des objets choisis, val la valeur totale emportée et m la masse totale
dans le sac
selection(L, mmax )
1: choix ←[]
2: val, m, i ←0, 0, 0
3: tant que i < taille(L) et m ≤ mmax faire
4: v i, invm i, ratio i ←L[i]
5: si m+ 1/invm i ≤ mmax alors
6: [Link](L[i])
7: val ←val + v i
8: m ←m + 1/invm i
9: fin si
10: i ←i + 1
11: fin tant que
12: renvoi: choix, val, m

2.2.4 Autres exemples classiques

On utilise également des algorithmes gloutons pour obtenir rapidement une solution aux problèmes difficiles
suivant :
• optimisation d’une ressource :
◦ Exemple : occupation d’une salle de classe par le plus de professeurs ou le plus de temps possible.
◦ Exemple : location d’un véhicule au plus grand nombre de clients.
• gestion de priorité :
◦ Exemple : jeter le moins de produits à cause de leur date de péremption.
• minimisation du nombre d’arrêts :
◦ Exemple : connaissant la localisation des stations essence sur un trajet on cherche où faire le plein pour
s’arrêter le moins souvent.

Lycée Carnot - Dijon MPSI & PCSI - Algorithmes I Méthodes par dichotomie
et algorithmes gloutons