Algorithmes gloutons

Notons $G=(g_1,\dots ,g_k)$ les activités choisies par le glouton, dans l'ordre, et soit $O=(o_1,\dots ,o_m)$ une sélection optimale, rangée par dates de fin croissantes. Montrons d'abord, par récurrence sur $i$, que le glouton finit toujours au plus tard en même temps : $f(g_i)\le f(o_i)$ pour tout $i\le \min (k,m)$.

Base : $g_1$ est, parmi toutes les activités, l'une de celles qui finissent le plus tôt — en particulier $f(g_1)\le f(o_1)$. Hérédité : supposons $f(g_i)\le f(o_i)$. L'activité $o_{i+1}$ commence après $f(o_i)\ge f(g_i)$ : elle était donc compatible avec les choix du glouton au moment où celui-ci a choisi $g_{i+1}$, et disponible. Le glouton ayant pris l'activité compatible qui finit le plus tôt, $f(g_{i+1})\le f(o_{i+1})$. ✓

Supposons alors $m>k$. L'activité $o_{k+1}$ commence après $f(o_k)\ge f(g_k)$ : elle est compatible avec toute la sélection gloutonne — mais alors le glouton, qui parcourt toutes les activités, l'aurait acceptée (elle ou une autre) comme $(k+1)$-ième choix : contradiction avec le fait qu'il s'est arrêté à $k$. Donc $m=k$ : le glouton est optimal. (Le cœur de l'argument : « le choix glouton ne ferme aucune porte » — toute solution optimale peut être échangée, activité par activité, contre la solution gloutonne sans perdre en cardinal. C'est le schéma de preuve à retenir, et à réutiliser tel quel pour les salles.)

Disons que l'algorithme ouvre $s$ salles, et considérons l'instant $d^{\ast }$ où la $s$-ième est ouverte : l'activité qui arrive commence en $d^{\ast }$ et aucune des $s-1$ salles n'est libre — chacune héberge une activité qui a commencé avant $d^{\ast }$ (tri par débuts) et finit après $d^{\ast }$. Il existe donc $s$ activités simultanément en cours à l'instant $d^{\ast }$. Or deux activités simultanées ne peuvent partager une salle : toute solution utilise au moins $s$ salles. Notre allocation en utilise exactement $s$ : elle est minimale. (La preuve exhibe un certificat : $s$ activités deux à deux incompatibles. Le nombre minimal de salles est ainsi coincé entre notre solution, qui en donne $s$, et le certificat, qui en exige $s$ — encadrement parfait, et l'occasion de noter que la borne inférieure se lit sur le problème, pas sur l'algorithme.)

À la main : $263=200+50+10+2+1$ — cinq pièces ($263-200=63$, $63-50=13$, $13-10=3$, $3-2=1$, $1-1=0$). La machine confirme : rendu_monnaie(263, [200, 100, 50, 20, 10, 5, 2, 1]) renvoie [200, 50, 10, 2, 1]. Le système euro étant canonique (admis), ce rendu de $5$ pièces est optimal : aucune décomposition de $263$ en valeurs du système n'utilise $4$ pièces ou moins. (Petit contrôle de cohérence indépendant : avec $4$ pièces au plus et une valeur maximale de $200$, on atteint au mieux $200\times 4=800\ge 263$ — l'argument grossier ne suffit donc pas à conclure, et c'est bien la canonicité qui travaille.)

Testons les montants croissants. Pour $m<10$, le glouton n'utilise que $7$ et $1$ : $7+1+\dots$ est clairement optimal (une seule façon raisonnable). Pour $m=14$ : glouton $=10+1+1+1+1$ ($5$ pièces) ; or $14=7+7$ ($2$ pièces) — non optimal, et les montants $10,\dots ,13$ se vérifient un à un favorables au glouton ($10=10$ ; $11=10+1$ ; $12=10+1+1$ contre $7+1\cdot 5$ : le glouton gagne ; $13=10+1+1+1$ contre $7+1\cdot 6$ : le glouton gagne). Le plus petit contre-exemple est donc $\boxed{14}$. (La méthode vaut mieux que le résultat : énumérer les petits montants, comparer glouton et optimal — à la main ici, par programme dès que le système grossit ; c'est l'exercice 27 de la banque.)

Tri par date de fin : $E(8,9)$, $A(8,10)$, $G(9,11)$, $B(9,12)$, $C(11,13)$, $D(12,14)$, $F(13,16)$. Parcours : $E$ prise (fin courante $9$) ; $A$ rejetée ($8<9$) ; $G$ prise ($9\ge 9$ — bornes : la fin est exclue, $[9,11[$ commence quand $[8,9[$ s'achève ; fin courante $11$) ; $B$ rejetée ($9<11$) ; $C$ prise ($11\ge 11$, fin $13$) ; $D$ rejetée ($12<13$) ; $F$ prise ($13\ge 13$). Sélection : $\{E,G,C,F\}$, cardinal $4$.

Optimalité : par le théorème du cours, le glouton est optimal — mais vérifions par certificat direct : à tout choix de $5$ activités, le principe des tiroirs appliqué aux quatre créneaux $[8,9[$, $[9,11[$, $[11,13[$, $[13,16[$… est ici inutilement subtil ; le plus simple est d'observer que les fins s'étalent de $9$ à $16$ et que cinq intervalles disjoints exigeraient une durée totale d'au moins $5\times 1=5$ dans $[8,16[$, ce qui ne conclut pas non plus — la preuve générale du cours est, de fait, le bon argument, et c'est précisément sa valeur : elle dispense de l'examen cas par cas. (Honnêteté de méthode : quand le certificat ad hoc devient laborieux, c'est le théorème général qu'il faut citer.)

Tri par début : $E(8,9)$, $A(8,10)$, $G(9,11)$, $B(9,12)$, $C(11,13)$, $D(12,14)$, $F(13,16)$ — le tri lexicographique de sorted départage les débuts égaux par la fin : $E$ passe avant $A$, $G$ avant $B$. Parcours : $E\to$ salle 1 (fin $9$) ; $A$ : salle 1 occupée ($9>8$) $\to$ salle 2 (fin $10$) ; $G$ : salle 1 libre ($9\le 9$) $\to$ salle 1 (fin $11$) ; $B$ : salle 1 ($11>9$) non, salle 2 ($10>9$) non $\to$ salle 3 (fin $12$) ; $C(11,13)$ : salle 1 libre ($11\le 11$) $\to$ salle 1 (fin $13$) ; $D(12,14)$ : salle 1 ($13>12$) non, salle 2 ($10\le 12$) oui $\to$ salle 2 (fin $14$) ; $F(13,16)$ : salle 1 ($13\le 13$) $\to$ salle 1. Trois salles.

Certificat : à l'instant $t=9,5$ par exemple, $A(8,10)$, $B(9,12)$ et $G(9,11)$ sont toutes trois en cours — trois activités deux à deux incompatibles : toute solution exige au moins $3$ salles. Le glouton en utilise $3$ : optimal. (Le déroulé montre l'instant exact où la troisième salle s'ouvre — l'arrivée de $B$ — et c'est bien là que vit le certificat, comme dans la preuve générale.)

Quand on peut fractionner, le bon critère est la valeur au kilo : $30/6=5$, $20/5=4$, $24/4=6$. Tri décroissant : la denrée à $6$/kg ($4$ kg), puis celle à $5$/kg ($6$ kg), puis celle à $4$/kg. Le sac prend $4$ kg (valeur $24$), puis $6$ kg (valeur $30$) — il est plein : valeur totale $\boxed{54}$.

Critère « plus grande valeur d'abord » : on prend les $6$ kg de valeur $30$, puis $4$ kg sur les $5$ kg de valeur $20$ (fraction $4/5$, valeur $16$) : total $46<54$ — sous-optimal.

L'optimalité de la valeur au kilo se voit par échange : si une solution emporte du poids d'une denrée moins dense alors qu'il reste de la plus dense, remplacer un gramme de l'une par un gramme de l'autre augmente la valeur — toute solution optimale remplit donc le sac par densités décroissantes, ce que fait le glouton. (Retenir le distinguo, qui prépare l'exercice 8 : fractionnable $\Rightarrow$ le glouton par densité est optimal ; indivisible $\Rightarrow$ il ne l'est plus.)

Critère : servir par durées croissantes (le plus court d'abord). Intuition : la durée du premier client est subie par les $n-1$ suivants, celle du deuxième par $n-2$, etc. — la somme des attentes vaut ${\sum }_i(n-i)t_{\sigma (i)}$ : il faut affecter les grands coefficients aux petites durées.

Preuve d'échange : soit un ordre optimal où deux clients consécutifs vérifient $t_a>t_b$ ($a$ passe juste avant $b$). Échangeons-les : seules leurs attentes mutuelles changent — avant l'échange, $b$ attend $t_a$ de plus ; après, $a$ attend $t_b$ de plus ; la somme varie de $t_b-t_a<0$ : elle diminue strictement, contredisant l'optimalité. Donc dans tout ordre optimal, les durées consécutives sont croissantes — l'ordre croissant est optimal. (L'argument « si deux voisins violent le critère, les échanger améliore » est la forme la plus pure de la preuve d'échange ; on remarquera son parfum de tri à bulles — corriger les inversions du critère — ce qui n'est pas un hasard : trier selon le bon critère est l'algorithme.)

Faisabilité : il faut $p_{i+1}-p_i\le K$ pour tout $i$ — sinon un tronçon est infranchissable, quel que soit l'algorithme.

Glouton : partir le plein fait, et à chaque arrêt, aller le plus loin possible — s'arrêter à la dernière station atteignable.

def arrets(p: list, K: int) -> list:
    """p : positions croissantes, p[0] = 0 = départ, p[-1] = arrivée.
    Renvoie les positions des arrêts (hors départ/arrivée)."""
    stops, position = [], 0
    i = 0
    while p[i] != p[-1]:
        # aller à la dernière station accessible depuis 'position'
        while i + 1 < len(p) and p[i + 1] - position <= K:
            i += 1
        stops.append(p[i])
        position = p[i]
    return stops[:-1] if stops and stops[-1] == p[-1] else stops

Preuve (échange, version « le glouton domine ») : notons $g_1<g_2<\dots$ les positions des arrêts gloutons et $o_1<o_2<\dots$ ceux d'une solution optimale. Par récurrence, $g_j\ge o_j$ pour tout $j$ : au premier arrêt, le glouton va par définition aussi loin que possible, donc $g_1\ge o_1$ ; et si $g_j\ge o_j$, le glouton repart d'au moins aussi loin et choisit de nouveau le point accessible le plus lointain, donc $g_{j+1}\ge o_{j+1}$. Le glouton, toujours en avance, atteint l'arrivée avec au plus autant d'arrêts. (Variante du schéma d'échange dite « le glouton reste devant » — la même qui prouvait $f(g_i)\le f(o_i)$ pour les activités : repérer cette structure de preuve dans les deux cas est tout l'enjeu du chapitre.)

Les sous-ensembles tenant dans $10$ kg : $\{1\}\to 30$ ; $\{2\}\to 20$ ; $\{3\}\to 24$ ; $\{1,3\}\to 6+4=10$ kg, valeur $54$ ; $\{2,3\}\to 9$ kg, valeur $44$ ; $\{1,2\}\to 11$ kg : trop lourd ; $\{1,2,3\}$ : trop lourd. Optimum : $54$ avec $\{1,3\}$.

Les gloutons : par valeur — prend $(6,30)$, puis $(5,20)$ ne tient pas, puis $(4,24)$ tient : $\{1,3\}$, valeur $54$… optimal ici ! Construisons alors mieux : remplaçons l'objet 2 par $(5\text{kg},26)$. Énumération : $\{1,3\}\to 54$ ; $\{2,3\}\to 50$ ; $\{1\}\to 30$… optimum toujours $54$. Par valeur : prend $(6,30)$ puis $(5,26)$ ne tient pas puis $(4,24)$ : $54$ — encore optimal. Le contre-exemple demande un peu plus de soin : capacité $10$, objets $(7,42)$, $(5,25)$, $(5,25)$. Par valeur et par densité ($6$ ; $5$ ; $5$) : prennent $(7,42)$, plus rien ne tient — valeur $42$ ; par poids croissant : $(5,25)+(5,25)=50$… qui est l'optimum (l'énumération le confirme : $42$, $50$, $25$ sont les seules valeurs atteignables). Donc valeur et densité échouent ($42<50$). Pour faire chuter aussi le poids croissant : capacité $10$, objets $(4,8)$, $(5,9)$, $(10,30)$ — poids croissant prend $(4,8)$ puis $(5,9)$ : $17$ ; l'optimum est $(10,30)\to 30$. Aucun des trois critères n'est correct en général. (Le sac à dos indivisible est un problème difficile au sens fort — comme la somme de sous-ensemble du chapitre 6, dont il est cousin ; le glouton y sert de solution approchée, jamais garantie. La frontière exacte avec l'exercice 5 tient en un mot : la divisibilité — qui autorise l'argument d'échange « gramme contre gramme », impossible sur des objets entiers.)

Supposons les deux listes triées : $t_1\le \cdots \le t_n$ et $h_1\le \cdots \le h_n$ ; le glouton apparie $t_i$ avec $h_i$. Soit $\sigma$ un appariement optimal quelconque : s'il contient un croisement — deux indices avec $t_a\le t_b$ appariés à $h_{\sigma (a)}\ge h_{\sigma (b)}$ — décroisons-les (apparier $t_a\to h_{\sigma (b)}$ et $t_b\to h_{\sigma (a)}$). Vérifions que le maximum des deux écarts ne croît pas : en notant $u\le v$ les tailles et $x\le y$ les hauteurs, il s'agit de voir

$$\max (|u-x|,|v-y|)\le \max (|u-y|,|v-x|).$$

Or les quatre points $u\le v$ et $x\le y$ sur la droite réelle vérifient : $|u-x|\le \max (|u-y|,|v-x|)$ (si $x\le u$, alors $|u-x|=u-x\le v-x$ ; sinon $|u-x|=x-u\le y-u$) et de même pour $|v-y|$. ✓ Chaque décroisement supprime au moins une inversion entre les deux listes sans augmenter le critère : en itérant (le nombre d'inversions est un variant !), on atteint l'appariement croissant du glouton, de critère au plus égal — il est optimal. (Trois chapitres se rejoignent : la preuve d'échange du jour, le variant du chapitre 1, et les inversions du chapitre 3. L'inégalité centrale — « apparier dans l'ordre n'aggrave jamais le pire écart » — resservira sous d'autres habits, des files d'attente aux statistiques.)

import random

def compatibles(sel: list) -> bool:
    s = sorted(sel)
    return all(s[i][1] <= s[i + 1][0] for i in range(len(s) - 1))

def optimum_brut(activites: list) -> int:
    meilleur = 0
    for sous in sous_listes(activites):          # chapitre 6 : 2**n candidats
        if compatibles(sous):
            meilleur = max(meilleur, len(sous))
    return meilleur

def plus_courte_d_abord(activites: list) -> list:
    tri = sorted(activites, key=lambda a: a[1] - a[0])
    choisies = []
    for (d, f) in tri:
        if all(f <= d2 or f2 <= d for (d2, f2) in choisies):
            choisies.append((d, f))
    return choisies

random.seed(7)
echecs, ecart_total, essais = 0, 0, 2000
for _ in range(essais):
    acts = []
    for _ in range(random.randint(1, 8)):        # petites instances : 2**8 max
        d = random.randint(0, 20)
        acts.append((d, d + random.randint(1, 6)))
    opt = optimum_brut(acts)
    assert len(selection_activites(acts)) == opt          # JAMAIS d'écart
    courte = len(plus_courte_d_abord(acts))
    if courte < opt:
        echecs += 1
        ecart_total += opt - courte
print(echecs / essais, ecart_total / max(echecs, 1))
#  2 % d'échecs (39 sur 2000 avec cette graine), écart moyen 1 quand il y a échec

Le banc confirme expérimentalement le théorème — aucun écart pour le critère par date de fin sur $2000$ instances — et chiffre la faillite du critère naïf : il échoue sur une petite fraction des instances — environ une sur cinquante ici —, généralement d'une activité ; rare ne veut pas dire correct : un seul échec suffit à réfuter. (Trois usages de ce banc : conjecturer (un glouton qui survit à $10^4$ instances aléatoires mérite qu'on tente la preuve), réfuter (le premier échec est un contre-exemple, que le banc peut afficher), et mesurer (un glouton faux peut rester une bonne heuristique — décision d'ingénieur, à prendre chiffres en main). La force brute exponentielle, inutilisable en production, trouve ici son vrai métier : juge de paix sur petites instances.)