Scribd
Importer
8 vues2 pages

Résolution de Problèmes de Reines et Tic-Tac-Toe

Le document présente des exercices sur la représentation et la résolution de problèmes, notamment le placement de reines sur un échiquier et le jeu Tic-tac-toe. Il demande des représentations en espace d'états et des résolutions à l'aide d'algorithmes de recherche. Enfin, il inclut un tableau à compléter sur les méthodes de recherche.

Transféré par

mariemrouissi615
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
8 vues2 pages

Résolution de Problèmes de Reines et Tic-Tac-Toe

Le document présente des exercices sur la représentation et la résolution de problèmes, notamment le placement de reines sur un échiquier et le jeu Tic-tac-toe. Il demande des représentations en espace d'états et des résolutions à l'aide d'algorithmes de recherche. Enfin, il inclut un tableau à compléter sur les méthodes de recherche.

Transféré par

mariemrouissi615
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

FSEG- Nabeul 2ème BC

TD n°3 : Représentation et résolution de problèmes


Exercice 1
On dispose d’un échiquier (8*8). On veut placer 8 reines sue l’échiquier sans laisser la possibilité
d’attaque de l’une par l’autre par ligne colonne ou diagonale.

1) Proposez une représentation en espace d’états de ce problème (sans représenter le graph


d’états).
2) Proposez une représentation en espace d’états de ce même problème mais pour un
échiquier (4*4) où on veut placer uniquement 4 reines et représentez le graphe d’états.

Exercice 2
On considère le jeu Tic-tac-toe qui se joue sur une grille carrée de 3x3 cases. Deux joueurs
s'affrontent. Ils doivent remplir chacun à leur tour une case de la grille avec le symbole qui leur est
attribué : O ou X. Le gagnant est celui qui arrive à aligner trois symboles identiques,
horizontalement, verticalement ou en diagonale.
Proposez une représentation en espace d’états de ce problème.

Exercice 3
Résolvez le problème des 4 reines de l’exercice 1 par :
1) L’algorithme de recherche en largeur d'abord.
2) L’algorithme de recherche en profondeur d'abord préfixé, infixé et suffixé.
3) Pour cet exercice, quelle est la meilleure stratégie de recherche ? Justifiez ?

Dr. Mouna Ben Ishak 1/2


FSEG- Nabeul 2ème BC

Exercice 4
Complétez le tableau suivant

Méthodes aveugles
Prise en compte des
connaissances spécifiques
au problème
Réduction de l'espace de
recherche
Exemple A*

Dr. Mouna Ben Ishak 2/2

Vous aimerez peut-être aussi