Corrigé X-ENS 2025 Informatique B MP-PC-PSI — Partie III (Q8 à Q9) : Recherche gloutonne à horizon limité

Sujet officiel du concours X-ENS, session 2025, épreuve Informatique B MP-PC-PSI. Corrigé rédigé par Ibrahim Alame.

Énoncé

Pour réduire le coût, on limite l'horizon à un petit entier $k$ . Partant de $(0, 0)$ , on calcule par la recherche exhaustive de la partie II (trouve_complet_rec avec l'horizon $k$ ) la meilleure suite locale, de poids minimal et d'au plus $k$ sauts ; on joue ces sauts, puis on recommence depuis la case atteinte, jusqu'à l'arrivée $(N - 1, N - 1)$ . Si aucune suite locale n'est trouvée, l'algorithme abandonne. Grille de l'introduction (sauts $\to$ , $↙$ , $↘$ par défaut, case bonus $(1, 2)$ activant $↓$ ) :


T = [[2, -4, -6, 0], [1, -2, 2, 3], [-2, 2, -3, 4], [-1, 4, -3, 7]]
sauts = [(0, 1), (1, -1), (1, 1)]
bonus = {(1, 2): [(1, 0)]}

Le chemin optimal pèse $- 7$ : $(0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2), (3, 2), (3, 3)$ .

Q8. Chemin trouvé pour $k = 2$ ; est-il optimal ? Mêmes questions pour $k = 3$ . Augmenter $k$ donne-t-il toujours un chemin de poids plus petit ?
Q9. Écrire trouve_glouton(T, sauts, bonus, k), qui renvoie (poids, sauts) pour le chemin trouvé, et (INFINI, []) si une recherche locale échoue.

Corrigé

Q8. On applique l'algorithme pas à pas, avec la convention de Q6 : une suite locale fait exactement $k$ sauts, sauf si elle atteint l'arrivée avant. Son poids compte la case de départ de l'étape, ce qui ne change pas la comparaison entre suites partant de la même case. Les sauts bonus ne sont disponibles qu'après le passage par $(1, 2)$ .

Pour $k = 2$ .

Depuis $(0, 0)$ : la meilleure suite est $\to, \to$ , vers $(0, 2)$ , de poids $2 - 4 - 6 = - 8$ . Les autres valent au mieux $- 3$ ( $↘, ↘$ ).
Depuis $(0, 2)$ : $↙, ↘$ vers $(2, 2)$ , de poids $- 6 - 2 - 3 = - 11$ , devant $↙, ↙$ vers $(2, 0)$ , de poids $- 10$ . La case bonus n'est pas visitée.
Depuis $(2, 2)$ , sans le saut $↓$ : $\to, ↙$ ou $↙, \to$ mènent à $(3, 2)$ avec le poids $- 3 + 4 - 3 = - 2$ . C'est une égalité, que le code de Q9 tranche par l'ordre de la liste sauts. Le saut direct $↘$ coûte $- 3 + 7 = 4$ .
Depuis $(3, 2)$ : $\to$ atteint l'arrivée.

Chemin trouvé : $(0, 0), (0, 1), (0, 2), (1, 1), (2, 2), (2, 3), (3, 2), (3, 3)$ , de poids $2 - 4 - 6 - 2 - 3 + 4 - 3 + 7 = - 5$ . L'autre choix à l'égalité passe par $(3, 1)$ au lieu de $(2, 3)$ , avec le même poids. Il n'est pas optimal : $- 5 > - 7$ .

Pour $k = 3$ .

Depuis $(0, 0)$ : $\to, \to, ↙$ vers $(1, 1)$ , de poids $2 - 4 - 6 - 2 = - 10$ . Les autres valent au mieux $- 8$ ( $\to, \to, \to$ ).
Depuis $(1, 1)$ : $\to$ vers la case bonus $(1, 2)$ , qui active $↓$ , puis $↓, ↓$ vers $(3, 2)$ , de poids $- 2 + 2 - 3 - 3 = - 6$ . Les autres suites font au mieux $- 5$ ( $↙, \to, \to$ ).
Depuis $(3, 2)$ : $\to$ atteint l'arrivée.

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 →