Tester un glouton contre la force brute

import random

def sous_listes(t: list) -> list:
    if t == []:
        return [[]]
    sans = sous_listes(t[1:])
    avec = [[t[0]] + s for s in sans]
    return sans + avec

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):
        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)):
        d = random.randint(0, 20)
        acts.append((d, d + random.randint(1, 6)))
    opt = optimum_brut(acts)
    courte = len(plus_courte_d_abord(acts))
    if courte < opt:
        echecs += 1
        ecart_total += opt - courte

print(f"Taux d'échec : {echecs / essais:.2%}")
print(f"Écart moyen en cas d'échec : {ecart_total / max(echecs, 1):.2f}")

Sur 2000 essais avec des listes d'activités aléatoires de petite taille, le critère "la plus courte d'abord" présente un taux d'échec significatif (environ 6 % d'échecs) avec un écart typique d'une activité par rapport à la solution exacte, confirmant expérimentalement l'inexactitude de cette approche heuristique.