X/ENS Informatique A MP 2017

ECOLE POLYTECHNIQUE -- ECOLES NORMALES SUPERIEURES

CONCOURS D'ADMISSION 2017

FILIERES

MP SPECIALITE INFO

COMPOSITION D'INFORMATIQUE ­ A ­ (XULCR)
(Duree : 4 heures)
L'utilisation des calculatrices n'est pas autorisee pour cette epreuve.
Le langage de programmation sera obligatoirement Caml.

Jeux a un joueur et solutions optimales
Nous nous interessons ici a des jeux a un joueur ou une configuration initiale est donnee
et ou le joueur effectue une serie de deplacements pour parvenir a une configuration gagnante.
Des casse-tete tels que le Rubik's Cube, le solitaire, l'ane rouge ou encore le taquin entrent dans
cette categorie. L'objectif de ce probleme est d'etudier differents algorithmes pour trouver des
solutions a de tels jeux qui minimisent le nombre de deplacements effectues.
La partie I introduit la notion de jeu a un joueur et un premier algorithme pour trouver
une solution optimale. Les parties II et III proposent d'autres algorithmes, plus efficaces. La
partie IV a pour objectif de trouver une solution optimale au jeu du taquin.
Les parties I, II et III peuvent etre traitees independamment. Neanmoins, chaque partie
utilise des notations et des fonctions introduites dans les parties precedentes. La partie IV
suppose qu'on a lu entierement l'enonce de la partie III.

Complexite
Par complexite en temps d'un algorithme A on entend le nombre d'operations elementaires
(comparaison, addition, soustraction, multiplication, division, affectation, test, etc) necessaires
a l'execution de A dans le cas le pire. Par complexite en espace d'un algorithme A on entend
l'espace memoire minimal necessaire a l'execution de A dans le cas le pire. Lorsque la complexite
en temps ou en espace depend d'un ou plusieurs parametres 0 , · · · , r-1 , on dit que A a une
complexite en O(f (0 , · · · , r-1 )) s'il existe une constante C > 0 telle que, pour toutes les valeurs
de 0 , · · · , r-1 suffisamment grandes (c'est-a-dire plus grandes qu'un certain seuil), pour toute
instance du probleme de parametres 0 , · · · , r-1 , la complexite est au plus C f (0 , · · · , r-1 ).

1

BFS()
A  {e0 }
p0
tant que A 6= 
B
pour tout x  A
si x  F alors
renvoyer VRAI
B  s(x)  B
AB
pp+1
renvoyer FAUX
Figure 1 ­ Parcours en largeur.

Partie I. Jeu a un joueur, parcours en largeur
Un jeu a un joueur est la donnee d'un ensemble non vide E, d'un element e0  E, d'une
fonction s : E  P(E) et d'un sous-ensemble F de E. L'ensemble E represente les etats possibles
du jeu. L'element e0 est l'etat initial. Pour un etat e, l'ensemble s(e) represente tous les etats
atteignables en un coup a partir de e. Enfin, F est l'ensemble des etats gagnants du jeu. On dit
qu'un etat ep est a la profondeur p s'il existe une sequence finie de p + 1 etats
e0 e1 . . . ep
avec ei+1  s(ei ) pour tout 0  i < p. Si par ailleurs ep  F , une telle sequence est appelee une solution du jeu, de profondeur p. Une solution optimale est une solution de profondeur minimale. On notera qu'un meme etat peut etre a plusieurs profondeurs differentes. Voici un exemple de jeu : E = N? e0 = 1 s(n) = { 2n, n + 1 } (1) Question 1. Donner une solution optimale pour ce jeu lorsque F = { 42 }. Parcours en largeur. Pour chercher une solution optimale pour un jeu quelconque, on peut utiliser un parcours en largeur. Un pseudo-code pour un tel parcours est donne figure 1. Question 2. Montrer que le parcours en largeur renvoie VRAI si et seulement si une solution existe. Question 3. On se place dans le cas particulier du jeu (1) pour un ensemble F arbitraire pour lequel le parcours en largeur de la figure 1 termine. Montrer alors que la complexite en temps et en espace est exponentielle en la profondeur p de la solution trouvee. On demande de montrer que la complexite est bornee a la fois inferieurement et superieurement par deux fonctions exponentielles en p. 2 DFS(m, e, p) si p > m alors
renvoyer FAUX
si e  F alors
renvoyer VRAI
pour chaque x dans s(e)
si DFS(m, x, p + 1) = VRAI alors
renvoyer VRAI
renvoyer FAUX
Figure 2 ­ Parcours en profondeur (partie II), limite par une profondeur maximale m.
Programmation. Dans la suite, on suppose donnes un type etat et les valeurs suivantes pour
representer un jeu en Caml :
initial: etat
suivants: etat -> etat list
final: etat -> bool
Question 4. Ecrire une fonction bfs: unit -> int qui effectue un parcours en largeur a
partir de l'etat initial et renvoie la profondeur de la premiere solution trouvee. Lorsqu'il n'y a
pas de solution, le comportement de cette fonction pourra etre arbitraire.
Indication : On pourra avantageusement realiser les ensembles A et B par des listes, sans
chercher a eliminer les doublons, et utiliser une fonction recursive plutot qu'une boucle while.
Question 5. Montrer que la fonction bfs renvoie toujours une profondeur optimale lorsqu'une
solution existe.

Partie II. Parcours en profondeur
Comme on vient de le montrer, l'algorithme BFS permet de trouver une solution optimale
mais il peut consommer un espace important pour cela, comme illustre dans le cas particulier du
jeu (1) qui necessite un espace exponentiel. On peut y remedier en utilisant plutot un parcours
en profondeur. La figure 2 contient le pseudo-code d'une fonction DFS effectuant un parcours
en profondeur a partir d'un etat e de profondeur p, sans depasser une profondeur maximale m
donnee.
Question 6. Montrer que DFS(m, e0 , 0) renvoie VRAI si et seulement si une solution de
profondeur inferieure ou egale a m existe.
Recherche iteree en profondeur. Pour trouver une solution optimale, une idee simple
consiste a effectuer un parcours en profondeur avec m = 0, puis avec m = 1, puis avec m = 2,
etc., jusqu'a ce que DFS(m, e0 , 0) renvoie VRAI.
Question 7. Ecrire une fonction ids: unit -> int qui effectue une recherche iteree en profondeur et renvoie la profondeur d'une solution optimale. Lorsqu'il n'y a pas de solution, cette
fonction ne termine pas.
3

Question 8. Montrer que la fonction ids renvoie toujours une profondeur optimale lorsqu'une
solution existe.
Question 9. Comparer les complexites en temps et en espace du parcours en largeur et de la
recherche iteree en profondeur dans les deux cas particuliers suivants :
1. il y a exactement un etat a chaque profondeur p ;
2. il y a exactement 2p etats a la profondeur p.
On demande de justifier les complexites qui seront donnees.

Partie III. Parcours en profondeur avec horizon
On peut ameliorer encore la recherche d'une solution optimale en evitant de considerer
successivement toutes les profondeurs possibles. L'idee consiste a introduire une fonction h :
E  N qui, pour chaque etat, donne un minorant du nombre de coups restant a jouer avant de
trouver une solution. Lorsqu'un etat ne permet pas d'atteindre une solution, cette fonction peut
renvoyer n'importe quelle valeur.
Commencons par definir la notion de distance entre deux etats. S'il existe une sequence de
k + 1 etats x0 x1 · · · xk avec xi+1  s(xi ) pour tout 0  i < k, on dit qu'il y a un chemin de longueur k entre x0 et xk . Si de plus k est minimal, on dit que la distance entre x0 et xk est k. On dit alors que la fonction h est admissible si elle ne surestime jamais la distance entre un etat et une solution, c'est-a-dire que pour tout etat e, il n'existe pas d'etat f  F situe a une distance de e strictement inferieure a h(e). On procede alors comme pour la recherche iteree en profondeur, mais pour chaque etat e considere a la profondeur p on s'interrompt des que p + h(e) depasse la profondeur maximale m (au lieu de s'arreter simplement lorsque p > m). Initialement, on fixe m a h(e0 ). Apres chaque
parcours en profondeur infructueux, on donne a m la plus petite valeur p + h(e) qui a depasse m
pendant ce parcours, le cas echeant, pour l'ensemble des etats e rencontres dans ce parcours. La
figure 3 donne le pseudo-code d'un tel algorithme, appele IDA? , ou la variable globale min est
utilisee pour retenir la plus petite valeur ayant depasse m.
Question 10. Ecrire une fonction idastar: unit -> int qui realise l'algorithme IDA? et
renvoie la profondeur de la premiere solution rencontree. Lorsqu'il n'y a pas de solution, le
comportement de cette fonction pourra etre arbitraire. Il est suggere de decomposer le code en
plusieurs fonctions. On utilisera une reference globale min dont on precisera le type et la valeur
retenue pour representer .
Question 11. Proposer une fonction h admissible pour le jeu (1), non constante, en supposant
que l'ensemble F est un singleton {t} avec t  N? . On demande de justifier que h est admissible.
Question 12. Montrer que, si la fonction h est admissible, la fonction idastar renvoie toujours
une profondeur optimale lorsqu'une solution existe.

4

def

def

IDA? () =
DFS? (m, e, p) =
m  h(e0 )
c  p + h(e)
tant que m 6= 
si c > m alors
min  
si c < min alors si DFS? (m, e0 , 0) = VRAI alors min  c renvoyer VRAI renvoyer FAUX m  min si e  F alors renvoyer FAUX renvoyer VRAI pour chaque x dans s(e) si DFS? (m, x, p + 1) = VRAI alors renvoyer VRAI renvoyer FAUX Figure 3 ­ Pseudo-code de l'algorithme IDA? . Partie IV. Application au jeu du taquin Le jeu du taquin est constitue d'une grille 4 × 4 dans laquelle sont disposes les entiers de 0 a 14, une case etant laissee libre. Dans tout ce qui suit, les lignes et les colonnes sont numerotees de 0 a 3, les lignes etant numerotees du haut vers le bas et les colonnes de la gauche vers la droite. Voici un etat initial possible : 0 1 2 3 0 2 3 1 6 1 14 5 8 4 2 12 7 9 3 10 13 11 0 On obtient un nouvel etat du jeu en deplacant dans la case libre le contenu de la case situee au-dessus, a gauche, en dessous ou a droite, au choix. Si on deplace par exemple le contenu de la case situee a droite de la case libre, c'est-a-dire 12, on obtient le nouvel etat suivant : 2 3 1 6 14 5 8 4 7 9 10 13 11 0 12 Le but du jeu du taquin est de parvenir a l'etat final suivant : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5 Ici, on peut le faire a l'aide de 49 deplacements supplementaires et il n'est pas possible de faire moins. Question 13. En estimant le nombre d'etats du jeu du taquin, et la place memoire necessaire a la representation d'un etat, expliquer pourquoi il n'est pas realiste d'envisager le parcours en largeur de la figure 1 pour chercher une solution optimale du taquin. Fonction h. On se propose d'utiliser l'algorithme IDA? pour trouver une solution optimale du taquin et il faut donc choisir une fonction h. On repere une case de la grille par sa ligne i (avec 0  i  3, de haut en bas) et sa colonne j (avec 0  j  3, de gauche a droite). Si e est un etat du taquin et v un entier entre 0 et 14, on note eiv la ligne de l'entier v dans e et ejv la colonne de l'entier v dans e. On definit alors une fonction h pour le taquin de la facon suivante : h(e) = 14 X |eiv - bv/4c| + |ejv - (v mod 4)|. v=0 Question 14. Montrer que cette fonction h est admissible. Programmation. Pour programmer le jeu de taquin, on abandonne l'idee d'un type etat et d'une fonction suivants, au profit d'un unique etat global et modifiable. On se donne pour cela une matrice grid de taille 4 × 4 contenant l'etat courant e ainsi qu'une reference h contenant la valeur de h(e). grid: int vect vect h: int ref La matrice grid est indexee d'abord par i puis par j. Ainsi grid.(i).(j) est l'entier situe a la ligne i et a la colonne j. Par ailleurs, la position de la case libre est maintenue par deux references : li: int ref lj: int ref La valeur contenue dans grid a cette position est non significative. Question 15. Ecrire une fonction move: int -> int -> unit telle que move i j deplace
l'entier situe dans la case (i, j) vers la case libre supposee etre adjacente. On prendra soin de
bien mettre a jour les references h, li et lj. On ne demande pas de verifier que la case libre est
effectivement adjacente.

Deplacements et solution. De cette fonction move, on deduit facilement quatre fonctions
qui deplacent un entier vers la case libre, respectivement vers le haut, la gauche, le bas et la
droite.
6

let
let
let
let

haut
gauche
bas
droite

()
()
()
()

=
=
=
=

move
move
move
move

(!li + 1) !lj;;
!li (!lj + 1);;
(!li - 1) !lj;;
!li (!lj - 1);;

Ces quatre fonctions supposent que le mouvement est possible.
Pour conserver la solution du taquin, on se donne un type deplacement pour representer
les quatre mouvements possibles et une reference globale solution contenant la liste des
deplacements qui ont ete faits jusqu'a present.
type deplacement = Gauche | Bas | Droite | Haut
solution: deplacement list ref
La liste !solution contient les deplacement effectues dans l'ordre inverse, i.e., la tete de liste
est le deplacement le plus recent.
Question 16. Ecrire une fonction tente gauche: unit -> bool qui tente d'effectuer un
deplacement vers la gauche si cela est possible et si le dernier deplacement effectue, le cas
echeant, n'etait pas un deplacement vers la droite. Le booleen renvoye indique si le deplacement
vers la gauche a ete effectue. On veillera a mettre a jour solution lorsque c'est necessaire.
On suppose avoir ecrit de meme trois autres fonctions
tente_bas
: unit -> bool
tente_droite: unit -> bool
tente_haut : unit -> bool
Question 17. Ecrire une fonction dfs: int -> int -> bool correspondant a la fonction
DFS? de la figure 3 pour le jeu du taquin. Elle prend en argument la profondeur maximale m
et la profondeur courante p. (L'etat e est maintenant global.)
Question 18. En deduire enfin une fonction taquin: unit -> deplacement list qui renvoie
une solution optimale, lorsqu'une solution existe.

Note : Trouver une solution au taquin n'est pas tres complique, mais trouver une
solution optimale est nettement plus difficile. Avec ce qui est propose dans la derniere
partie de ce sujet, on y parvient en moins d'une minute pour la plupart des etats
initiaux et en une dizaine de minutes pour les problemes les plus difficiles.

7