X/ENS Informatique A MP 2017

Thème de l'épreuve Jeux à un joueur et solutions optimales
Principaux outils utilisés algorithmes, graphes, complexité
Mots clefs parcours de graphes, parcours en largeur, parcours en profondeur, taquin, horizon, IDA

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                    

Rapport du jury

(télécharger le PDF)
           

Énoncé obtenu par reconnaissance optique des caractères


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 

Extrait du corrigé obtenu par reconnaissance optique des caractères


 X/ENS Informatique A MP 2017 -- Corrigé Ce corrigé est proposé par Benjamin Monmege (enseignant-chercheur à l'université) ; il a été relu par William Aufort (professeur en CPGE). Ce sujet propose la résolution de jeux à un joueur tels que le Rubik's Cube, le solitaire ou le taquin, qui fait d'ailleurs l'objet de la dernière partie. Ces jeux peuvent être modélisés à l'aide d'un graphe orienté dont les sommets sont les configurations du jeu et les arcs sont les coups possibles à partir de chaque état. Le but du jeu est d'atteindre une configuration finale. Il s'agit donc d'un objectif d'accessibilité, que l'on résout à l'aide de parcours en largeur ou en profondeur. Il est important de traiter les quatre parties dans l'ordre. · La première partie introduit le modèle de jeu avec un exemple simple, puis propose une première résolution utilisant un parcours en largeur. · La deuxième partie étudie ensuite une option qui s'appuie sur le parcours en profondeur. Puisque l'on cherche une solution optimale en nombre de coups pour atteindre une configuration finale, la recherche se fait de manière itérée en augmentant progressivement la profondeur. · La troisième partie étudie l'algorithme IDA qui affine la recherche itérée en profondeur en introduisant une fonction d'horizon qui estime (sans jamais surestimer) la distance entre une configuration et une solution du jeu. Cela permet d'explorer nettement moins de configurations, au prix de la recherche manuelle d'une fonction d'horizon admissible. · Finalement, la quatrième partie applique l'algorithme IDA au jeu de taquin en proposant une fonction d'horizon. Le sujet est très intéressant. Il contient plusieurs questions assez délicates demandant de prouver la correction ou la complexité des algorithmes de parcours étudiés. Les fonctions OCaml à écrire sont, pour la plupart, des retranscriptions d'algorithmes donnés par l'énoncé ; il faut cependant être vigilant sur les transformations à apporter. Dans l'ensemble, c'est un bon énoncé pour réviser les parcours de graphes. Le problème est assez motivant, puisqu'à la fin on obtient un code complet pour la résolution du jeu de taquin. Dans le corrigé, les codes sont écrits en OCaml plutôt qu'en Caml Light, comme le demandait pourtant l'énoncé, car c'est le langage qui est devenu obligatoire aux concours à partir de la session 2019. Indications Partie I 1 L'énoncé ne demande pas de justifier l'optimalité de la solution proposée. 2 Montrer d'abord par récurrence sur p N, inférieur à la profondeur d'une solution optimale du jeu, qu'au début de la p-ième itération de la boucle tant que, l'ensemble A contient l'ensemble des états à profondeur p. 3 Relier les complexités en temps et en espace avec le nombre d'états insérés dans B. Pour la minoration, il faut faire attention au fait que les doublons ne comptent pas dans la complexité spatiale. Cependant, on pourra par exemple montrer que tous les entiers entre 1 et 2i ont été insérés dans B lors d'au moins une des 2i premières étapes. 4 Faire attention au changement de type entre le pseudo-code, qui renvoie un booléen, et la fonction bfs demandée, qui doit renvoyer la profondeur optimale. 5 Utiliser les arguments avancés lors de la question 2. Partie II 6 Montrer par récurrence descendante sur p [[ 0 ; m + 1 ]] que pour tout état e, DFS(m, e, p) renvoie VRAI si et seulement si une solution de profondeur au plus m - p existe depuis l'état e. 7 Commencer par implémenter une fonction dfs réalisant le parcours en profondeur avant de l'utiliser dans la fonction ids. 8 Utiliser la question 6. 9 Huit résultats de complexité sont ici demandés, avec justification : il vaut mieux remplir un tableau pour être sûr de ne pas en oublier. Pour la recherche itérée en profondeur, ne pas oublier de compter l'espace mémoire requis par la pile d'appels récursifs. Partie III 10 On pourra utiliser la constante max_int, définie par le langage OCaml comme la plus grande valeur de type int, pour représenter la valeur . S'inspirer ensuite des fonctions de la question 7. 11 Essayer avec h(n) = log2 (t/n), pour tout n 6 t. 12 Reprendre la récurrence de la question 6. Expliquer ensuite l'effet sur la variable min de l'appel à DFS (m, e0 , 0) (appelée avec la valeur initiale pour min). Partie IV 13 Connaître le nombre d'états permet de minorer l'espace mémoire nécessaire pour représenter un état. Conclure en utilisant l'information délivrée par l'énoncé que le nombre de déplacements nécessaire pour résoudre le taquin peut être de l'ordre de 50. 15 Il est inutile de recalculer h : il suffit de mettre à jour sa valeur en observant que peu de termes changent. On pourra utiliser la fonction abs d'OCaml pour calculer la valeur absolue d'un élément de type int. 17 S'inspirer de la fonction réalisant l'algorithme DFS de la question 10 en modifiant le test pour savoir si la grille est finale (utiliser la fonction h pour cela) et l'énumération des voisins. Lors de cette énumération, si un voisin ne convient pas, ne pas oublier de revenir en arrière en remettant à jour la grille et la liste !solution. I. Jeu à un joueur, parcours en largeur 1 Les coups optimaux du jeu sont liés à la décomposition en binaire des entiers de F. Dans le cas où F = {42}, l'écriture binaire de 42 est 101010, ce qui peut s'écrire 42 = 2 × (1 + 2 × 2 × (1 + 2 × 2 × 1)) À partir de 1, on multiplie donc deux fois par 2, puis on ajoute 1, puis à nouveau on multiplie deux fois par 2, avant d'ajouter 1 et de multiplier une dernière fois par 2. Ainsi, on en déduit que La séquence 1 2 4 5 10 20 21 42 est une solution optimale du jeu, de profondeur 7. L'énoncé ne demande pas de prouver l'optimalité et le rapport insiste sur le fait qu'il était inutile de perdre du temps à la prouver. Cependant, il n'est pas très difficile de montrer par récurrence sur n N que la profondeur d'une solution optimale lorsque F = {n} est égale à (k - 1) + (u - 1), avec k = 1 + log2 n le nombre de chiffres dans l'écriture binaire ak-1 ak-2 · · · a1 a0 de n et u = Card ({i [[ 0 ; k - 1 ]] | ai = 1}) le nombre de bits à 1 dans cette écriture binaire. On trouve aussi la solution optimale : le terme k - 1 est le nombre de multiplications par 2 à effectuer, et le terme u - 1 est le nombre d'incrémentations. Une autre stratégie pour trouver la solution consiste à énumérer l'ensemble des entiers de profondeur 1, 2, 3, etc. jusqu'à trouver le nombre 42 : c'est d'ailleurs plus ou moins l'idée de la partie III. 2 Montrons par récurrence que la propriété P(p) : « au début de la p-ième itération de la boucle tant que, l'ensemble A contient l'ensemble des états à profondeur p » est vraie pour tout p N inférieur à la profondeur d'une solution optimale du jeu. · P(0) est vraie car A est initialisé à {e0 }, e0 étant l'unique état à profondeur 0. · P(p) = P(p + 1) : supposons qu'au début de la p-ième itération de la boucle tant que l'ensemble A contient l'ensemble des états à profondeur p et que p est strictement inférieur à la profondeur d'une solution optimale du jeu. La boucle pour tout considère les états de A et ajoute dans B tous leurs successeurs par s. D'après l'hypothèse sur p, le test x F ne sera jamais satisfait, puisque cela impliquerait que le jeu possède une solution optimale de profondeur p. Un état e ayant profondeur p + 1 si et seulement s'il existe un état e ayant profondeur p tel que s(e ) = e, on a bien que B contient l'ensemble des états à profondeur p + 1 à la fin de l'itération. La mise à jour de l'ensemble A avec l'ensemble B permet d'obtenir P(p + 1). · Conclusion : pour tout p N inférieur à la profondeur d'une solution optimale du jeu, P(p) est vraie. Ainsi, si une solution existe de profondeur p minimale, lors de la p-ième itération de la boucle tant que, le test x F permet de renvoyer VRAI. Sinon, aucune solution n'existe, donc ce test n'est jamais concluant. Il y a alors deux possibilités : soit le programme ne s'arrête jamais (et ne renvoie donc pas VRAI), soit il s'arrête du fait que A devient vide, auquel cas le programme renvoie FAUX. Finalement, Le parcours en largeur renvoie VRAI si et seulement si une solution existe. Rappelons que BFS est le sigle de breadth-first search, le nom anglais du parcours en largeur. 3 Le nombre d'opérations élémentaires effectuées par le parcours en largeur est de l'ordre du nombre d'éléments insérés dans B au total, c'est-à-dire le nombre total d'occurrences d'états atteignables depuis e0 (il peut y avoir des doublons) avant d'arriver à la profondeur p où un état de F est atteint pour la première fois. Ce nombre est inférieur au nombre de séquences possibles de longueur au plus p : puisqu'il y a deux coups possibles à chaque étape, le nombre total d'états insérés dans B est ainsi majoré par p P i=1 2i = 2p+1 - 1 Minorons ensuite ce nombre d'états insérés dans B. Montrons que, pour i N, tous les entiers entre 1 et 2i ont été insérés dans B lors d'au moins une des 2i premières étapes. Fixons donc un entier n [[ 1 ; 2i ]]. Son écriture en binaire est de la forme ak ak-1 · · · a1 a0 avec k 6 i et ak = 1 : on peut ainsi décomposer n sous la forme n= k P j=0 aj 2j = a0 + 2 × (a1 + 2 × (a2 + · · · + 2 × (ak-1 + 2 × ak ) · · · )) Par conséquent, il existe une séquence d'au plus 2k 6 2i états allant de 1 à n : on commence par aller de 1 à 2 × ak = 2 en une étape, puis vers 2 × (ak-1 + 2 × ak ) en une ou deux étapes supplémentaires, etc. jusqu'à l'ajout éventuel de a0 en au plus une étape. Ainsi, p étant la profondeur de la solution trouvée, tous les entiers entre 1 et 2p/2 ont été insérés. On a donc inséré au moins 2p/2 > ( 2)p-1 états distincts dans B lors du parcours en largeur, ce qui donne un minorant de la complexité en temps. Considérons ensuite la complexité en espace. L'espace mémoire requis est de l'ordre de la taille maximale de l'ensemble B, majorée par le nombre d'états atteignables à la profondeur p, inférieur à 2p . Pour obtenir une minoration, utilisons la borne 2p/2 sur le nombre total d'états distincts insérés dans B : puisqu'on réalise p étapes, le principe des tiroirs assure qu'il y a au moins une étape qui insère 2p/2 /p éléments distincts dans B. Or, pour tout entier p supérieur à 16, on a p 6 2p/4 , de sorte que 2p/2 2(p-1)/2 2p/4 > = p/4 p 2 2 ce qui minore donc la complexité en espace par une fonction exponentielle de p, pour p assez grand. Ainsi, Dans le cas particulier du jeu (1) pour un ensemble F arbitraire pour lequel le parcours en largeur de la figure 1 termine, la complexité en temps et en espace est exponentielle en la profondeur p de la solution trouvée. 4 Représentons les ensembles A et B par des listes a et b d'états et utilisons une fonction auxiliaire récursive voisins : etat list -> etat list -> int -> int pour simuler les deux boucles tant que et pour tout simultanément. Ainsi, l'appel à voisins [initial] [] 0 renvoie la profondeur d'une solution du jeu, si le jeu admet une solution, ou renvoie une erreur si elle s'arrête sans avoir trouver de solution (il se peut aussi que la fonction ne s'arrête jamais).