IMERIR Examen d'Intelligence Artificielle 2° année
2007/2008 Jeudi 20 décembre 2007 Carmack
Modalités: Durée: 2 heures
Aucun document autorisé. Ni calculatrice, ni téléphone portable.
Aucune sortie n'est autorisée pendant la durée de l'examen.
Excepté pour les questions de cours 1 à 3, une réponse sans explication de la méthode employée, ni sans détailler
les étapes de construction de la réponse n'a aucune valeur!
I. Questions de cours (5 points)
Pour les questions 1 à 3 vous répondrez sur votre copie en notant simplement le numéro de la question et le(s)
numéro(s) de(s) la réponse(s) correspondante(s) (les questions peuvent avoir plusieurs réponses possibles).
e.g. : question 0 réponses c et d
1) La complexité en espace de l'algorithme de recherche en profondeur d'abord pour un facteur de branchement
b et une profondeur maximale finie m est en :
a) O(bm)
b) O(b+m)
c) O(pm)
d) O(b*m)
2) Soit π=(X,D,C,R) le CSP défini par :
X={X1,X2,X3}
D1=D2=D3={1;2;3}
C={C1={X1;X2};C2={X2;X3};C3={X1;X3}}
R1={(1,2);(1,1);(3,1);(2,2)}
R2={(2,1);(3,1);(3,2);(1,2)}
R3={(1,3);(3,1);(1,2);(2,1)}
Parmi les affirmations suivantes la/les quelle(s) est/sont exacte(s) ?
a) π est arc consistant,
b) π n'est pas arc consistant,
c) D1 est arc consistant
d) D1 n'est pas arc consistant
3) L'algorithme de recherche en profondeur itérative est un algorithme :
a) adéquat
b) complet
c) optimal
4) (2 points) Soient le graphe de l'exercice III et l'heuristique h2 donnée ci dessous pour la recherche de plus
court chemin de A à I par l'algorithme A*.
A B C D E F G H I J
h2 15 15 15 11 15 11 6 6 6 0
a) Dites si l'heuristique h2 est admissible ou non pour A*.
b) Justifiez votre réponse.
1/3 E. Salvat 26/08/2008
IMERIR Examen d'Intelligence Artificielle 2° année
2007/2008 Jeudi 20 décembre 2007 Carmack
II. α−β (5 points)
Dans le jeu que nous considérons ici, on part d'une pile de n jetons. A tour de rôle, les deux joueurs doivent
diviser en deux piles non vides et de tailles différentes une des piles devant eux. A chaque tour du jeu, on crée
donc une nouvelle pile. A partir d'une configuration du jeu comportant 3 piles à 2, 3 et 2 jetons, le seul coup
jouable est de diviser la pile de 3 jetons en 2 et 1 jeton. Le joueur qui ne peut plus jouer a perdu.
Question 1 :
Appliquez l'algorithme α−β avec au départ une pile de 7 jetons.
Question 2 :
Qui est le vainqueur?
III. A* (4 points)
Soit le graphe suivant, la valeur portée sur chaque arc correspond au coût de passage d'une extrémité de l'arc à
l'autre. On souhaite calculer le plus court chemin de A à J.
3 11 I
A E
12
5
8
2
7
1
4 9 G 6
B C J
4
2
4
5
D 3 F 2
H
On a de plus la fonction heuristique h qui estime le coût pour atteindre J depuis chaque sommet. h est donnée par
le tableau ci dessous.
A B C D E F G H I J
h 16 14 10 11 13 7 4 7 6 0
Question :
Appliquez l'algorithme A* avec la fonction h sur ce graphe.
2/3 E. Salvat 26/08/2008
IMERIR Examen d'Intelligence Artificielle 2° année
2007/2008 Jeudi 20 décembre 2007 Carmack
IV. Les stars de l'ATP (6 points)
L'ATP-tour est composé de 6 étapes sur la planète : 4 dans l'hémisphère nord, 2 dans l'hémisphère Sud. Les
tournois ont tous leur sponsor. Les six tournois sont :
Tournois Pays Sponsor
Roland Garros (RG) France (Fr) Coq Sportif (CS)
Wimbledon (W) Angleterre (GB) Reebok (Rk)
Cincinnati (Ci) Etats Unis d'Amérique (USA) Coq Sportif (CS)
US Open (USO) Etats Unis d'Amérique (USA) Nike (Nk)
Open d'Australie (OA) Australie (Au) Reebok (Rk)
Open de Sydney (OS) Australie (Au) Nike (Nk)
Nous nous intéressons à 4 joueurs vedettes en particulier : Cédric, Boris, André et Diane. Chacun ayant des
spécialités (Simple Homme SH, Double Homme DH, Double Mixte DM) et ses propres sponsors, ils ont
quelques contraintes quant à leur participation aux différents tournois.
– Cédric participe à Roland Garros, Wimbledon, et l'US Open, mais ne joue pas lorsque le sponsor est Nike. Il
ne joue qu'en Simple Homme.
– Boris ne participe pas aux tournois de l'hémisphère Sud. Il ne joue pas lorsque le sponsor est Nike ou
Reebok. En joueur complet il particpe en simple homme, double homme, et double mixte .
– André, américain très patriote, ne joue qu'aux USA et lorsque le sponsor est le Coq Sportif. Il joue en simple
homme et double mixte.
– Diane, comme son nom l'indique est la seule représentante de la gente féminine que l'on suit. Elle ne joue
jamais lorsque le sponsor est Reebok. Et bien sûr, ne joue qu'en double mixte.
En tant que responsable du service des sports de DOO (LA chaîne sportive internationale qui émet 24h/24), vous
cherchez à savoir à quel(s) tournoi(s) chaque star va jouer et dans quel(s) type(s) de rencontre(s).
Question 1 :
Proposez un CSP qui permette de représenter le problème.
Question 2 :
Résolvez le CSP que vous avez proposé à l'aide de l'algorithme du Forward Checking. On cherche TOUTES les
solutions.
3/3 E. Salvat 26/08/2008
IMERIR Examen d'Intelligence Artificielle 2° année
2007/2008 Jeudi 20 décembre 2007 Carmack
Modalités: Durée: 2 heures
Aucun document autorisé. Ni calculatrice, ni téléphone portable.
Aucune sortie n'est autorisée pendant la durée de l'examen.
Excepté pour les questions de cours 1 à 3, une réponse sans explication de la méthode employée, ni sans
détailler les étapes de construction de la réponse n'a aucune valeur!
I. Questions de cours (5 points)
Pour les questions 1 à 3 vous répondrez sur votre copie en notant simplement le numéro de la question et le(s)
numéro(s) de(s) la réponse(s) correspondante(s) (les questions peuvent avoir plusieurs réponses possibles).
e.g. : question 0 réponses c et d
1) La complexité en espace de l'algorithme de recherche en profondeur d'abord pour un facteur de branchement
b et une profondeur maximale finie m est en :
a) O(bm)
b) O(b+m)
c) O(pm)
d) O(b*m)
2) Soit π=(X,D,C,R) le CSP défini par :
X={X1,X2,X3}
D1=D2=D3={1;2;3}
C={C1={X1;X2};C2={X2;X3};C3={X1;X3}}
R1={(1,2);(1,1);(3,1);(2,2)}
R2={(2,1);(3,1);(3,2);(1,2)}
R3={(1,3);(3,1);(1,2);(2,1)}
Parmi les affirmations suivantes la/les quelle(s) est/sont exacte(s) ?
a) π est arc consistant,
b) π n'est pas arc consistant,
c) D1 est arc consistant
d) D1 n'est pas arc consistant
3) L'algorithme de recherche en profondeur itérative est un algorithme :
a) adéquat
b) complet
c) optimal
4) (2 points) Soient le graphe de l'exercice III et l'heuristique h2 donnée ci dessous pour la recherche de plus
court chemin de A à J par l'algorithme A*.
A B C D E F G H I J
h2 15 15 15 11 15 11 6 6 6 0
a) Dites si l'heuristique h2 est admissible ou non pour A*.
Réponse : NON
b) Justifiez votre réponse.
1/7 E. Salvat 05/05/2010
IMERIR Examen d'Intelligence Artificielle 2° année
2007/2008 Jeudi 20 décembre 2007 Carmack
Réponse : h2(F) = 11. Or le chemin de F à J F-H-G-J, a un coût de 10. Cette heuristique n'est donc
pas optimiste : h2(F) > val(F,J)
II. α−β (5 points)
Dans le jeu que nous considérons ici, on part d'une pile de n jetons. A tour de rôle, les deux joueurs doivent
diviser en deux piles non vides et de tailles différentes une des piles devant eux. A chaque tour du jeu, on crée
donc une nouvelle pile. A partir d'une configuration du jeu comportant 3 piles à 2, 3 et 2 jetons, le seul coup
jouable est de diviser la pile de 3 jetons en 2 et 1 jeton. Le joueur qui ne peut plus jouer a perdu.
Question 1 :
Appliquez l'algorithme α−β avec au départ une pile de 7 jetons.
Réponse :
En bleu les valeurs d'appel de α et β, en rouge les valeurs de retour. Les chiffres de chaque sommet
représentent les différentes piles. par exemple « 5/1/1 » représente un jeu de trois piles : une contenant 5 jetons
et deux piles de un jeton.
2/7 E. Salvat 05/05/2010
IMERIR Examen d'Intelligence Artificielle 2° année
2007/2008 Jeudi 20 décembre 2007 Carmack
Max (-∞,+∞)
α=−1 7
-1 -1
-1
Min (-∞,+∞) (-1,+∞) (-1,+∞)
6/1 5/2 4/3
β=1 β=−1
-1
-1
-1
1
(-1,+∞) (-1,+∞)
(-∞,+∞) (-∞,1)
Max 5/1/1 4/2/1 4/2/1 3/2/2 3/3/1 4/2/1
α=1 α=−1 α=−1
α=−1
-1
-1
-1
-1
1
(1,+∞) (-∞,1) (-1,+∞) (-1,+∞)
(-∞,+∞)
Min 4/1/1/1 3/2/1/1 3/2/1/1 3/2/1/1 3/2/1/1
β=1 β=−1 β=−1 β=−1 β=−1
-1
-1
1
-1
-1
(-∞,+∞) (1,+∞) (-∞,1) (-1,+∞) (-1,+∞)
Max 3/1/1/1/1 2/2/1/1/1 2/2/1/1/1 2/2/1/1/1 2/2/1/1/1
α=1 −1 −1 −1
−1
1
(-∞,+∞)
Min 2/1/1/1/1/1
+1
Réponse :
L'algorithme calcule sur chaque noeud une valeur de retour. Sur les noeuds Max, on affecte α au maximum
entre sa valeur courante et la valeur de retours de chacun des fils des noeuds. Si la valeur de retour d'un fils
est supérieure ou égale à la valeur courante de β, on stoppe l'exploration des fils du noeud actuel, et l'on
retourne cette valeur. De même sur un noeud Min, on affecte β au minimum entre la valeur courante et la
valeur de retour de chacun des fils. Et lorsque la valeur de retour d'un fils est inférieure ou égale à α , on
stoppe l'exploration des fils du noeud actuel, et l'on retourne cette valeur.
Dans l'exemple ci-dessus, sur le noeud « 7 », de type Max, l'exploration de sous-arbre de racine « 6/1 » renvoie
la valeur -1. L'appel sur le noeud « 5/2 », de type Min et fils suivant de « 7 », se fait donc avec les valeurs de α
=-1 et β=+∞. Le retour de l'exploration du premier fils de « 5/2 » renvoie -1. Cette valeur étant égale (et donc
inférieure ou égale) à la valeur courante de α, on arrête l'exploration des fils de ce noeud, et on peut renvoyer
directement la valeur obtenue : -1.
Le même phénomène se produit pour le noeud « 4/3 ».
Bien entendu si l'on explore les différentes possibilités dans un autre ordre, on n'obtiendra pas exactement le
même arbre d'exploration ni les mêmes coupes!
Question 2 :
3/7 E. Salvat 05/05/2010
IMERIR Examen d'Intelligence Artificielle 2° année
2007/2008 Jeudi 20 décembre 2007 Carmack
Qui est le vainqueur?
Réponse :
Le vainqueur est Min !
III. A* (4 points)
Soit le graphe suivant, la valeur portée sur chaque arc correspond au coût de passage d'une extrémité de l'arc à
l'autre. On souhaite calculer le plus court chemin de A à J.
3 E 11 I
A
12
5
8
2
7
1
B 4 C 9 G 6
J
4
2
4
5
D 3 F 2
H 9
On a de plus la fonction heuristique h qui estime le coût pour atteindre J depuis chaque sommet. h est donnée
par le tableau ci dessous.
A B C D E F G H I J
h 16 14 10 11 13 7 4 7 6 0
Question :
Appliquez l'algorithme A* avec la fonction h sur ce graphe.
Réponse : On représente le déroulement de l'algorithme sous forme de tableau. Chaque ligne du tableau
correspond à un tour de boucle de l'algorithme. La première colonne indique le numéro de tour de l'algo, dans
la deuxième colonne on indique le sommet choisi. Dans la troisième colonne l'ensemble des ouverts de l'étape
courante est représenté, chaque état est noté sous le format « sommet(g(x),f(x)=g(x)+h(x)) ». La dernière
colonne contient l'ensemble des fermés de l'étape courante.
Etape Choix Ouverts Fermés
Init {A(0,16)} {}
1 A(0,16) {B(2,16);C(5,15);E(3,16)} {A(0,19)}
2 C(5,15) {B(2,16); E(3,16); D(9,20); F(9,16); G(14,18)} {A(0,16); C(5,15)}
3 B(2,16) {E(3,16); D(7,18); F(9,16); G(14,18)} {A(0,16); C(5,15); B(2,16)}
E(3,16) {D(7,18); F(9,16); G(14,18); C(4,14); {A(0,16); B(2,16); E(3,16)}
4 I(14,20)}
5 C(4,14) {D(7,18); F(8,15); G(13,17); I(14,20)} {A(0,16); B(2,16); E(3,16); C(4,14)}
6 F(8,15) {D(7,18); G(13,17); I(14,20); H(10,17)} {A(0,16); B(2,16); E(3,16); C(4,14); F(8,15)}
7 H(10,17) {D(7,18); G(12,16); I(14,20); J(19,19)} {A(0,16); B(2,16); E(3,16); C(4,14); F(8,15); H(10,17)}
8 G(12,16) {D(7,18); I(14,20); J(18,18)} {A(0,16); B(2,16); E(3,16); C(4,14); F(8,15); H(10,17);
G(12,16)}
4/7 E. Salvat 05/05/2010
IMERIR Examen d'Intelligence Artificielle 2° année
2007/2008 Jeudi 20 décembre 2007 Carmack
Etape Choix Ouverts Fermés
9 J(18,18)
Remarques :
– A l'initialisation, on met dans Ouverts, le sommet de départ;
– A chaque étape on choisit dans Ouverts un sommet s tel que f(s)=g(s)+h(s) soit minimal. Pour tous les
voisins v de s, si v n'appartient ni à Ouverts ni à fermés, on ajoute v à Ouverts. Sinon on remet v dans
Ouverts avec une nouvelle valeur de g(v) seulement si g(s)+coût(s->v) est inférieur à la valeur de g(v)
mémorisée.
– A l'étape 3, après sélection du sommet B, la valeur de g(D) dans Ouverts passe de 9 à 7;
– A l'étape 4, après sélection du sommet E, la valeur de g(C) passe de 5 à 4 et C passe des Fermés aux
Ouverts;
– A l'étape 5, les valeur de g de F et G dans Ouverts passent respectivement de 9 à 8 et de 14 à 13;
– A l'étape 7, la valeur de g de G dans Ouverts passe de 13 à 12;
– A l'étape 8, la valeur de g de J dans Ouverts passe de 19 à 18.
Le chemin le plus court de A à J est donc A-E-C-F-H-G-J, et est de longueur 18.
IV. Les stars de l'ATP (6 points)
L'ATP-tour est composé de 6 étapes sur la planète : 4 dans l'hémisphère nord, 2 dans l'hémisphère Sud. Les
tournois ont tous leur sponsor. Les six tournois sont :
Tournois Pays Sponsor
Roland Garros (RG) France (Fr) Coq Sportif (CS)
Wimbledon (W) Angleterre (GB) Reebok (Rk)
Cincinnati (Ci) Etats Unis d'Amérique (USA) Coq Sportif (CS)
US Open (USO) Etats Unis d'Amérique (USA) Nike (Nk)
Open d'Australie (OA) Australie (Au) Reebok (Rk)
Open de Sydney (OS) Australie (Au) Nike (Nk)
Nous nous intéressons à 4 joueurs vedettes en particulier : Cédric, Boris, André et Diane. Chacun ayant des
spécialités (Simple Homme SH, Double Homme DH, Double Mixte DM) et ses propres sponsors, ils ont
quelques contraintes quant à leur participation aux différents tournois.
– Cédric participe à Roland Garros, Wimbledon, et l'US Open, mais ne joue pas lorsque le sponsor est Nike. Il
ne joue qu'en Simple Homme.
– Boris ne participe pas aux tournois de l'hémisphère Sud. Il ne joue pas lorsque le sponsor est Nike ou
Reebok. En joueur complet il particpe en simple homme, double homme, et double mixte .
– André, américain très patriote, ne joue qu'aux USA et lorsque le sponsor est le Coq Sportif. Il joue en simple
homme et double mixte.
– Diane, comme son nom l'indique est la seule représentante de la gente féminine que l'on suit. Elle ne joue
jamais lorsque le sponsor est Reebok. Et bien sûr, ne joue qu'en double mixte.
En tant que responsable du service des sports de DOO (LA chaîne sportive internationale qui émet 24h/24),
vous cherchez à savoir à quel(s) tournoi(s) chaque star va jouer et dans quel(s) type(s) de rencontre(s).
5/7 E. Salvat 05/05/2010
IMERIR Examen d'Intelligence Artificielle 2° année
2007/2008 Jeudi 20 décembre 2007 Carmack
Question 1 :
Proposez un CSP qui permette de représenter le problème.
Question 2 :
Résolvez le CSP que vous avez proposé à l'aide de l'algorithme du Forward Checking. On cherche TOUTES les
solutions.
Réponse :
π =(X,D,C,R) avec :
– X={ T; P; S; J; Sp}
– D = { DT = { RG; W; Ci; USO; OA; OS}
DP = { Fr; GB; USA; Au}
DS = { CS; Rk; Nk}
DJ = { A; B; C; D}
DSp = { DH; SH; DM} }
– C={ C1={ J; T}; C2={ J; S}; C3={ J; Sp}; C4={ J; P}; C5={ T; P}; C6={ T; S} }
– R={ R1= {(C,RG); (C,W); (C,USO); (A,RG); (A,W); (A,Ci); (A,USO); (A,OA); (A,OS); (B,RG); (B,W);
(B,Ci); (B,USO); (B,OA); (B,OS); (D,RG); (D,W); (D,Ci); (D,USO); (D,OA); (D,OS) };
R2= { (C,CS); (C,Rk); (B,CS); (A,CS); (D,CS); (D,Nk) };
R3= { (C,SH); (B,SH); (B,DH); (B,DM); (A,SH); (A,DM); (D,DM) };
R4= { (C,Fr); (C,GB); (C,USA); (C,Au); (B,Fr); (B,GB); (B,USA); (A,USA); (D,Fr); D,GB); (D,USA);
(D,Au) };
R5= { (RG,Fr); (W,GB); (Ci,USA); (USO,USA); (OA,Au); (OS,Au) };
R6= { (RG,CS); (W,Rk); (Ci,CS); (USO,Nk); (OA,Rk); (OS,Nk)} }
6/7 E. Salvat 05/05/2010
J A B C D
D ={CS}
S DS={CS} DS={CS;Rk} DS={CS;Nk}
DP={USA} DP={Fr;GB;USA} DT={RG;W;USO} DSp={DM}
DSp={SH;DM} DSp={SH;DH;DM} DSp={SH}
S CS CS CS Rk Nk CSD ={RG;Ci}
DT={RG;Ci} DT={RG;Ci} DT={RG} DT={W} DT={USO;OS} T
DP={USA} DP={USA} DSp={SH} DSp={SH} DSp={DM} DSp={DM}
DSp={SH;DM} DSp={SH;DM}
T Ci RG RG Ci RG W USO OS RG Ci
DP={USA} DP={} DP={Fr} DP={USA} DP={Fr} DP={GB} DP={USA} DP={Au} DP={Fr} DP={USA}
DSp={SH;DM} DSp={SH;DH;DM} Dsp={SH; DSp={SH} DSp={SH} Dsp={DM} Dsp={DM} Dsp={DM} Dsp={DM}
DH;DM}
P USA Fr USA Fr GB USA Au Fr USA
DSp={SH;DM} DSp={SH;DH;DM} Dsp={SH; DSp={SH} DSp={SH} DSp={DM} DSp={DM} DSp={DM} DSp={DM}
DH;DM}
Sp SH DM SH DH DM SH DH DM SH SH DM DM DM DM
