| Programmez par plaisir! |
30-07-2010 03:41 |
Introduction
Description
Screenshots
Documentation
Téléchargements
Le but de ce projet est d'implémenter un algorithme A, A* et de l'appliquer au jeu du taquin afin de pouvoir résoudre un certain nombre de configurations. Pour rappel, le but du jeu du taquin est de reconstituer une image qui a été décomposée en petits carrés qui ont été mélangés.
1. Description de l'algorithme utilisé pour résoudre le jeu du taquin :
Fonction : recherche2
Arguments :
départ (* l'état initial *)
test_état_but (* un prédicat caractérisant les buts *)
fils_état (* retourne la liste des fils d'un état *)
estime_état (* estime la promesse d'un état, c'est-à-dire
l'intérêt d'exploiter l'état *)
classe (* range les fils d'un état dans la file d'attente selon le
critère défini par
estime_état *)
Variables locales :
file_attente (* la liste des états non encore explorés avec leur
valeur *)
vus (* la liste des états déjà explorés *)
prochain (* le prochain état à explorer *)
continuer (* un booléen *)
Algorithme :
début
file_attente <- {départ};
continuer <- vrai;
tant_que file_d'attente != Ø et
continuer faire
début
prochain <- pop(file_d'attente);
vus <- push(prochain, vus);
si test_état_but(prochain)
alors continuer <- faux
sinon
début
file_d'attente <- classe(file_d'attente, vus,
fils_état(prochain), estime_état)
(* appliquer fils_état à prochain pour produire les fils de
prochain, utiliser estime_état
pour rajouter les fils de prochain dans file_d'attente en les ordonnant du
meilleur vers
le moins prometteur *)
fin
fin_tant_que
si continuer alors afficher("chec")
sinon afficher ("succs")
fin
2. Test de l'algorithme sur un graphe :
Le graphe de la figure ci-dessous représente un "graphe de coût".
Chaque noeud Ui du graphe est associé à un état Ei (d'un espace d'états) et porte la
valeur de la fonction heuristique h(Ei) qui estime le coût du chemin optimum entre Ei et un des états
buts E15 ou E16. Chaque arc est associé à un opérateur de changement d'état. La valeur
numérique portée par l'arc dans le graphe de coût donne le coût réel de
l'opérateur associé dans l'espace d'états.
On peut vérifier (laborieusement) que la fonction h est minorante.
Le problème est de construire un chemin de coût minimum entre l'état E0 correspondant au noeud
U0 et un des états buts.
Chemin solution :
( E0 , 17 )
( E1 , 15 )
( E4 , 12 )
( E9 , 7 )
( E10 , 6 )
( E12 , 6 )
( E13 , 2 )
( E16 , 0 )
3. Application au jeu du taquin.
3.1 Heuristique W : cases non encore en place.
Cette heuristique est minorante et monotone. Elle consiste à prendre h(e) le nombre de cases qui ne sont pas,
dans l'état e, à la place exigée par l'état but b. Cette heuristique est simple mais elle
ne tient pas compte du nombre de coups pour amener une case pleine à sa destination dans l'état but b
selon qu'elle en est plus ou moins éloignée.
3.2 Heuristique P : somme des distances "en pâté de maison"
On utilise donc la distance "pâté de maison" (en anglais "city-block" ou "Manhattan" distance). Cette
heuristique est également minorante et monotone; elle n'est pas formellement mieux informée que W mais
l'expérience confirme qu'elle est beaucoup plus efficace. Si Le(c) et Ce(c) (resp. Lb(c) et Cb(c)
désignent les numéros de la ligne et de la colonne de la case c dans l'état e (resp. dans
l'état but), on définit : d(c, n, b) = | Le(c) - Lb(c) | + | Ce(c) - Cb(c) |
Alors h(n) est égal à la somme des distance d(x, e, b) des cases pleines. P est plus fine que W, mais
ne tient pas compte de la difficulté à inverser deux cases voisines.
3.3 Heuristique P+3S
Contrairement à W et P, cette heuristique ne peut s'utiliser que dans le cas du taquin 3x3. Pour un état
e, on définit d'abord S de la façon suivante :
- On choisit un sens de parcours des cases non centrales autour de la case centrale. On ne considère que les
cases non centrales différentes de la case vide. A chacune d'entre elles, on attribue :
- Un poids de 0 si elle est aussi non centrale dans l'état but b et si dans les deux états
(e et b) la case suivante (dans le sens de parcours choisi) est la mme.
- 2 sinon.
- A la case centrale, si elle est pleine dans l'état e, on attribue :
- 0 si elle est bien placée par rapport à b.
- 1 sinon.
On a donc S(e) = somme des poids des cases pleines dans l'état e et h(e) = P(e) + 3 * S(e).
Version textuelle.
Version graphique.
Version jouable.
Sujet. (pdf) [ 553 Ko ]
Le code source (tar.gz) [15 Ko]
Le code source (zip) [27 Ko]
Contenu de l'archive : (cliquable)
Graphe.ml,
GrapheTest.ml,
GrapheUtil.ml,
HeuristiqueP3S.ml,
HeuristiqueP.ml,
HeuristiqueW.ml,
ReadMe.txt,
Recherche1.ml,
Recherche2.ml,
Resultats.txt,
TaquinGraphic.ml,
TaquinGraphicTest.ml,
TaquinJouer.ml,
TaquinTest1bis.ml,
TaquinTest1.ml,
TaquinTest2bis.ml,
TaquinTest2.ml,
TaquinTest3bis.ml,
TaquinTest3.ml,
TaquinUtil.ml
