Corrigé Centrale 2025 Informatique MPI — Partie A, IV (Q17 à Q18) : Solution optimale par parcours en largeur, gestion de la mémoire

Q17. Le graphe des états a pour sommets les états accessibles depuis $e$ et un arc pour chaque mouvement ; on cherche la distance de $e$ au plus proche état gagnant. Les arcs ont tous le même coût $1$ : c'est un parcours en largeur, avec la file de la partie II et, pour l'ensemble des états déjà découverts, la table de hachage de la partie III.

int resout(etat *e) {
    tableh *vus = t_nouveau();
    file *f = f_nouveau();
    e->distance = 0;
    t_ajoute(vus, e);
    f_enfile(f, e);
    int resultat = -1;
    while (f->taille > 0) {
        etat *x = f_defile(f);
        if (e_gagne(x)) {
            resultat = x->distance;
            break;
        }
        deplacement *lst = e_deplacements(x);
        for (deplacement *d = lst; d != NULL; d = d->suivant) {
            etat *y = e_copie(x);
            vehicule *v = &y->v[d->k];
            if (v->direction == 'H') v->j += d->pas;
            else v->i += d->pas;
            if (t_contient(vus, y)) {
                e_libere(y);
            } else {
                y->distance = x->distance + 1;
                t_ajoute(vus, y);
                f_enfile(f, y);
            }
        }
        d_libere(lst);
    }
    f_libere(f);
    t_libere(vus);
    return resultat;
}

Correction. C'est le parcours en largeur du cours, à deux invariants près. (i) Tout état de la file est dans vus, et distance y vaut la longueur d'un chemin de $e$ à cet état ; un état n'est enfilé qu'une fois, lors de sa découverte. (ii) Les distances des états de la file, de la tête à la queue, sont croissantes au sens large et diffèrent d'au plus $1$. Il en découle, comme pour tout parcours en largeur, que les états sont défilés par distance croissante et que distance est la distance minimale depuis $e$ (un état découvert depuis $x$ ne peut pas l'avoir été plus tôt par un chemin plus court, sinon il serait déjà dans vus). Le premier état gagnant défilé réalise donc le nombre minimal de mouvements. Si la file se vide sans état gagnant, tous les états accessibles ont été examinés et aucun ne gagne : on renvoie $-1$. Le test t_contient repose sur e_egal, licite ici puisque tous les états comparés sont accessibles depuis $e$ (mêmes véhicules, mêmes indices ; Q13).