Corrigé Mines-Ponts 2025 Informatique commune MP-PC-PSI — Partie 6 (Q15 à Q17) : Séparation et évaluation sur un arbre de dictionnaires récursif

Sujet officiel du concours Mines-Ponts, session 2025, épreuve Informatique commune MP-PC-PSI. Corrigé rédigé par Ibrahim Alame.

Sujet officiel (PDF, site du concours)

Énoncé

Principe. Un algorithme par séparation et évaluation (PSE, branch and bound) élague de l'arbre des solutions les branches qui ne peuvent pas contenir l'optimum. Un glouton fournit d'abord un profit $P_{m i n}$ ; on cherche alors à maximiser $P$ sous les contraintes $\sum r_{i} x_{i} \leq b$ et $P > P_{m i n}$ .

Arbre. Chaque nœud est un dictionnaire à trois clés : 'S' (la liste $[x_{0}, \dots, x_{k - 1}]$ des choix faits à la profondeur $k$ , vide à la racine), 'g' et 'd' (les fils gauche, $x_{k} = 1$ , et droit, $x_{k} = 0$ ). À la profondeur $n$ , 'S' est une solution complète et les deux fils sont des dictionnaires vides \{\}. La fonction récursive construireArbreBinaire(a, n) construit cet arbre à partir de la racine \{'S':[], 'g':\{\, 'd':\{\}\}}.

Figure 2 — Arbre binaire partiel pour $n = 3$ , avec la valeur de 'S' à chaque nœud.

Q15. Écrire estFeuille(a) qui renvoie True si l'arbre a est une feuille.
Q16. Le profit glouton est dans la variable globale Pmin. Écrire possible(obj, Sk, b) ( $len(Sk) = k \in [[1, n]]$ ) qui renvoie True s'il est utile d'explorer sous ce nœud : contrainte doit être vraie pour Sk complétée par des $0$ jusqu'à la longueur $n$ , et profit de Sk complétée par des $1$ doit pouvoir battre le glouton.
Q17. La fonction récursive KPforceBrute(arbre, obj, b) déclare global Pmin, Sol ; sur une feuille admissible de profit $P > Pmin$ , elle met à jour Pmin et Sol (lignes 3 à 8) ; sinon (ligne 9, else:) elle s'appelle sur arbre['g'] puis sur arbre['d']. Renommée KPpse, réécrire la partie à partir de la ligne 9 pour élaguer les branches qui dépassent $b$ ou ne peuvent pas battre Pmin.

Corrigé

Q15. Par construction, un nœud est une feuille si et seulement si ses deux fils sont des dictionnaires vides (profondeur $n$ ) ; un nœud interne a toujours ses deux fils non vides.


def estFeuille(a: dict) -> bool:
    return a['g'] == {} and a['d'] == {}

On accède aux valeurs par leurs clés 'g' et 'd'. Ce que le correcteur attend : pas d'écriture du type a[0] ou « premier élément du dictionnaire » : a[0] cherche la clé 0 (ici absente, d'où une KeyError), un dictionnaire n'étant pas indexé par positions. Tester len(a['g']) == 0 convient aussi.

Q16. On fabrique les deux listes de longueur $n$ demandées par concaténation, ce qui crée de nouvelles listes et laisse Sk intacte.


def possible(obj: [(int)], Sk: [int], b: int) -> bool:
    n = len(obj)
    k = len(Sk)
    S0 = Sk + (n - k) * [0]     # objets restants tous refusés
    S1 = Sk + (n - k) * [1]     # objets restants tous acceptés
    return contrainte(obj, S0, b) and profit(obj, S1) > Pmin

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →