Corrigé Mines-Ponts 2026 Informatique II MPI — Partie 3 (Q24 à Q33) : A, heuristiques admissibles et monotones, A pondéré

Sujet officiel du concours Mines-Ponts, session 2026, épreuve Informatique II MPI. Corrigé rédigé par Ibrahim Alame.

Énoncé

L'algorithme A fonctionne comme Dijkstra, mais une salle $u$ est insérée dans la file de priorité avec la priorité $dist[u] + h (u)$ , où $h$ est une heuristique estimant le coût restant jusqu'à la salle destination $t$ , avec $h (t) = 0$ . On note $s$ la source, dist[u] le coût actuellement connu d'un chemin de $s$ à $u$ , et $δ (u, t)$ le coût minimal réel d'un chemin de $u$ à $t$ (coûts strictement positifs). $h$ est admissible si $h (u) ⩽ δ (u, t)$ pour toute salle $u$ ; elle est monotone* si $h (t) = 0$ et $h (u) ⩽ c + h (v)$ pour tout passage $u \to v$ de coût $c$ .

Q24. $h$ admissible (terminaison admise) : montrer, par l'absurde, que le chemin trouvé est de coût minimal dès que $t$ est extraite de la file de priorité.
Q25. Quel lien entre Dijkstra et A* permet d'en déduire l'optimalité de Dijkstra ?
Q26. Montrer qu'une heuristique monotone est admissible (chaîne d'inégalités le long d'un chemin).
Q27. Intérêt pratique de la monotonie : coût dist définitif à l'extraction, pas de réinsertion des salles traitées.

A* pondéré.

Pour $w > 1$ , la priorité devient $f (u) = dist[u] + w \cdot h (u)$ .

Q28. Comparer l'ordre d'exploration de Dijkstra et de A* (valeur d'extraction, effet de l'heuristique par rapport à la destination).
Q29. Effet du facteur $w$ sur le poids relatif de l'heuristique et sur l'ordre d'exploration.
Q30. Si $h$ est admissible, $h_{w} = w \cdot h$ l'est-elle encore ?
Q31. Effet d'une augmentation de $w$ sur le nombre de salles explorées et sur la qualité du chemin ; est-il toujours optimal ?
Q32. Pourquoi cette variante convient-elle aux moteurs de jeux anciens ?

Un chemin de $s$ à $t$ de coût $c$ est $w$ -optimal si $c ⩽ w \cdot δ (s, t)$ . L'algorithme A* pondéré, avec $h$ admissible, maintient best, coût du meilleur chemin complet de $s$ à $t$ trouvé jusqu'ici, et contient l'extrait :


/* Extrait de l'algorithme */
int u = tas_depile(t);

/* Condition : arrêt anticipé */
if (dist[u] + w * h(u) >= best) {
    break;
}

Q33. Montrer que l'arrêt sur cette condition garantit que le chemin renvoyé, de coût best, est $w$ -optimal : majorer $f (v)$ par $w \cdot δ (s, t)$ pour les salles $v$ d'un chemin optimal, en déduire $min f ⩽ w \cdot δ (s, t)$ , puis conclure avec la condition d'arrêt $min f ⩾ best$ .

Corrigé

Le modèle d'algorithme.

Comme en Q23, chaque fois que dist[v] diminue par relâchement d'un passage $u \to v$ , la salle $v$ est (ré)insérée avec sa nouvelle priorité, et une entrée périmée (dont la priorité ne correspond plus à la valeur courante de dist) est ignorée à l'extraction ; une salle extraite avec sa valeur courante est traitée : on relâche ses passages sortants. Sans hypothèse de monotonie, une salle déjà traitée dont dist diminue plus tard est donc réinsérée puis traitée à nouveau — c'est ce que Q27 permettra d'éviter. Deux faits servent partout : dist[v] est toujours le coût d'un chemin effectif de $s$ à $v$ , donc $dist[v] ⩾ δ (s, v)$ , et dist ne fait que décroître. On note $f$ la priorité ( $w = 1$ pour A*) et $δ (s, t)$ le coût minimal de $s$ à $t$ ; un sous-chemin d'un chemin de coût minimal est de coût minimal, donc pour toute salle $v$ d'un tel chemin, $δ (s, v) + δ (v, t) = δ (s, t)$ .

Lemme (salle « témoin »). Soit $P = (s = v_{0}, v_{1}, \dots, v_{k} = t)$ un chemin de coût minimal. Avant chaque extraction, si $dist[t] > δ (s, t)$ , il existe $i < k$ tel que $dist [v_{i}] = δ (s, v_{i})$ et que la file contienne une entrée de $v_{i}$ de priorité $δ (s, v_{i}) + w h (v_{i})$ .

Preuve. $dist[s] = 0 = δ (s, s)$ ; soit $i$ le plus grand indice tel que $dist [v_{i}] = δ (s, v_{i})$ ; $i < k$ par hypothèse. Au moment où dist $[v_{i}]$ a pris la valeur $δ (s, v_{i})$ (au départ si $i = 0$ ), $v_{i}$ a été insérée avec la priorité $δ (s, v_{i}) + w h (v_{i})$ . Si cette entrée avait déjà été extraite, elle n'était pas périmée (dist $[v_{i}]$ ne peut descendre sous $δ (s, v_{i})$ ), donc $v_{i}$ aurait été traitée avec cette valeur et le relâchement de $v_{i} \to v_{i + 1}$ aurait donné $dist [v_{i + 1}] ⩽ δ (s, v_{i}) + c (v_{i}, v_{i + 1}) = δ (s, v_{i + 1})$ , donc l'égalité, ce qui contredit la maximalité de $i$ . L'entrée est donc encore dans la file. $□$

Q24. Supposons, par l'absurde, qu'au moment où $t$ est extraite on ait $dist[t] > δ (s, t)$ (le chemin reconstruit a pour coût dist[t]). L'entrée de $t$ extraite a une priorité $⩾ dist[t] + h (t) = dist[t]$ , puisque $h (t) = 0$ et que dist[t] n'a pu que décroître depuis son insertion. Par le lemme ( $w = 1$ ), la file contenait une entrée de priorité

$δ (s, v_{i}) + h (v_{i}) ⩽ δ (s, v_{i}) + δ (v_{i}, t) = δ (s, t) < dist[t],$

la première inégalité étant l'admissibilité de $h$ . Or les salles sont extraites par valeur $dist[u] + h (u)$ croissante : la file aurait renvoyé cette entrée avant celle de $t$ . Contradiction : à l'extraction de $t$ , $dist[t] = δ (s, t)$ , et le chemin trouvé est de coût minimal.

Ce que le correcteur attend : un raisonnement par l'absurde mené à son terme, donc l'existence justifiée d'une salle du chemin optimal encore dans la file avec son coût exact (le lemme), et pas seulement l'inégalité $h (v) ⩽ δ (v, t)$ .

Q25. Dijkstra est A* avec l'heuristique nulle $h \equiv 0$ : la priorité $dist[u] + 0$ est celle de Dijkstra. Or $h \equiv 0$ est admissible, puisque $δ (u, t) ⩾ 0$ (coûts positifs), et vérifie $h (t) = 0$ . Le raisonnement de Q24 s'applique donc tel quel : quand Dijkstra extrait une salle $t$ , dist[t] est le coût minimal. Comme $t$ est quelconque, cela vaut pour toutes les salles, ce qui justifie aussi le Dijkstra sans destination de Q23.

Q26. Soit $h$ monotone, $u$ une salle et $u = v_{0}, v_{1}, \dots, v_{k} = t$ un chemin de coût minimal de $u$ à $t$ (il existe, le monde étant fortement connexe), de coûts de passages $c_{0}, \dots, c_{k - 1}$ , donc $δ (u, t) = \sum_{l = 0}^{k - 1} c_{l}$ . Montrons par récurrence descendante sur $j$ que

$h (v_{j}) ⩽ l = j \sum k - 1 c_{l} .$

Pour $j = k$ , c'est $h (t) = 0 ⩽ 0$ . Si c'est vrai au rang $j + 1$ , la monotonie sur le passage $v_{j} \to v_{j + 1}$ donne $h (v_{j}) ⩽ c_{j} + h (v_{j + 1}) ⩽ c_{j} + \sum_{l = j + 1}^{k - 1} c_{l} = \sum_{l = j}^{k - 1} c_{l}$ . Au rang $j = 0$ :

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 →