Solutionnaire

Université de Sherbrooke
Département d'informatique
IFT 615
Intelligence artificielle
Examen périodique
Hiver 2009 Le vendredi 27 février, 10 h 30 à 12 h 20, au D3-2037
Professeur
Froduald Kabanza
http://www.planiart.usherbrooke.ca/kabanza
SOLUTIONS Question 1 (5 points) - Satisfaction des contraintes On vous demande de concevoir un programme pour assigner des sièges lors
d'une réception d'un mariage. Nous avons N invités et M tables
circulaires, chacune avec une capacité de C (nombres de personnes maximales
par table). On suppose que le nombre de tables est suffisant pour le nombre
d'invités (MC ? N). Répondez le plus clairement possible aux questions
suivantes dans l'espace indiqué. a. (1 point) Supposons qu'on a des contraintes sur les personnes qui
doivent s'asseoir aux mêmes tables ou aux tables adjacentes (par exemple
des parents avec leurs enfants) et des paires de personnes qui ne peuvent
s'asseoir aux mêmes tables ou à des tables adjacents (par exemple les ex-
conjoints). Expliquez comment vous formaliseriez ce problème comme un
problème de satisfaction de contraintes.
|Définir une variable pour chaque invité : N variables au total. |
|Le domaine de chaque variable est l'ensemble des places : MN variables. |
|(On pourrait utiliser un seul identifiant pour chaque siège ou deux |
|(table,place-sur-la-table)). |
|On définit une fonction d'appartenance aux mêmes tables pour deux places |
|données. |
|On définit une fonction d'appartenance à deux tables adjacentes pour deux |
|places places données (ou d'adjacence de tables si on a choisi la deuxième |
|représentation) en fonction de la disposition des tables. |
|Pour chaque groupe de personnes devant s'asseoir aux mêmes tables ou aux tables|
|adjacentes, on définit des contraintes correspondantes. |
|Même choses pour les personnes qui ne doivent pas s'asseoir au mêmes tables ou|
|aux tables adjacentes |
b. (1 point) Proposez une technique (algorithme) pour résoudre ce
problème tel que formulé dans votre réponse précédente.
|Backtracking search avec MRV et AC3. |
c. (1 point) Tel qu'énoncé au point (a), les contraintes sont « dures »
(elles doivent être absolument satisfaites) et le problème pourrait ne
pas avoir de solution. Proposez un énoncé différent pour le problème
d'assignations de places dans un mariage, avec des contraintes plus
souples, tel que le problème puisse tout le temps avoir une solution.
|Plutôt que d'imposer des contraintes sur les placements des personnes sur les |
|tables, on exprime des préférences sur les placements de personnes sur les |
|tables. Pour ce faire, on exprime les contraintes comme avant; c-à-d., une |
|contrainte est une paire de personnes ne devant pas s'asseoir sur la même table|
|ou à une table adjacente; ou au contraire devant s'asseoir sur la même table où|
|à une table adjacente. En plus on donne une fonction de coût, prenant une |
|contrainte comme argument et retournant un nombre réel exprimant le coût lié à |
|la violation de la contrainte; ainsi la fonction exprime le degré de |
|désirabilité de la contrainte. Dorénavant on est sûr d'avoir toujours une |
|solution. Par contre, une solution retournée pourrait violer certaine |
|contraintes. |
d. (1 point) Expliquez comment vous formaliseriez le nouveau problème, tel
qu'énoncé dans votre réponse au point c, comme un problème de
satisfaction de contraintes.
|Même formalisation qu'avant, sauf qu'on ajoute en plus la fonction de coût qui |
|étant donnée une contrainte retourne un nombre réel exprimant le coût lié à la |
|violation de la contrainte. |
| |
| |
| |
e. (1 point) Proposez une technique (algorithme) pour résoudre le
nouveau problème tel que formulé dans votre réponse précédente.
|Utiliser A*. |
|Un n?ud est une assignation (partielle) comme dans Backtracking-Search |
|Comme dans Bakktracking-Search, dans un n?ud, on assigne une variable à la |
|fois. |
|Étant donné une assignation (partielle), définissons le coût de l'assignation |
|comme étant la somme des coûts des contraintes violées par l'assignation. |
|Le coût d'une transition entre deux assignations successives est la différence |
|des coûts entre ces transitions. |
|La fonction heuristique donne l'estimé du coût entre le n?ud courant |
|(assignation partielle) et une assignation complète optimale : |
|On pourrait la calculer en estimant le coût de la violation des contraintes par|
|les variables restantes |
|(c-à-d., les variables non encore présentes dans l'assignation partielle |
|courante). |
| |
|Il peut y avoir de meilleures fonctions h, mais c'est un véritable défi de les |
|définir. |
Question 2 (5 points) - Alpha-Beta Pruning (5 points) Soit l'espace d'états suivant modélisant les actions de deux
joueurs (MAX et MIN). Les feuilles correspondent aux états terminaux du
jeu. Les valeurs des états terminaux sont indiquées en bas de chaque état.
Dessinez la partie de l'espace d'états qui serait explorée par l'algorithme
alpha-beta pruning, en supposant qu'il explore l'espace d'états de la
gauche vers la droite. Dessinez seulement les états explorés et les
transitions correspondantes. Indiquez, à côté de chaque état exploré, la
valeur correspondante à la terminaison de l'algorithme. | |
| |
| |
| |
| |
| |
| |
| |
| |
| |
|Étiquettes : La valeur (v) du n?ud, ainsi que la paire [?, ?] à chaque n?ud, à|
|la terminaison de l'algorithme. |
|Rappel : |
|? : meilleure (plus grande) valeur de MAX jusqu'ici; elle ne décroît jamais; |
|MAX ne considère jamais les n?uds MIN successeurs (en bas de lui) ayant des |
|valeurs plus petites que ?. |
|? : meilleure (plus petite) valeur de MIN jusqu'ici; elle ne croît jamais; MIN |
|ne considère jamais les n?uds MAX successeurs (en bas de lui) ayant des valeurs|
|plus grandes que ?. |
|A a ? = 6 (A ne sera jamais plus petit|(La première fois qu'on atteint G, en |
|que 6) |descendant, on a [?, ?] = [-?,+?]. En |
|Ainsi, B est ? -coupé puisque 4 < ? =|remontant de H, [?, ?] = [3,+?]. En |
|6 |remontant de I, on a [?, ?] = [7,+?]). |
|C a ? = 6 (C ne sera jamais plus grand|F a ? = 7 (F ne sera jamais plus |
|que 6) |grand que 7) |
|Ainsi, D est ?-coupé puisque 14 > ? = 6|Ainsi, J est ?-coupé puisque 9 > ? = 7 |
| |A la fin, E = 7. |
Question 3 (5 points) - Réseaux bayésiens Soit le réseau bayésien (RB) suivant pour quatre variables booléennes
aléatoires (A, B, C et D) avec les tables de probabilité conditionnelle
correspondantes.
a. (1 point) Combien de valeurs indépendantes faudrait-il pour stocker la
distribution jointe des probabilités?
| |
|24 - 1 = 15. | b. (1 point) Pour ce réseau, est-ce vrai ou faux que P(A,C,D)=P(A)P(C)P(D)?
Justifiez votre réponse. | |
|Faux. |
|