Salut!
Je cherche l'Algorithme de résolution d'un Taquin(Slide puzzle)3x3.
Merci.
Version imprimable
Salut!
Je cherche l'Algorithme de résolution d'un Taquin(Slide puzzle)3x3.
Merci.
Salut.
Il n'y a pas 1 algorithme mais des tas.
Le premier algo qui me vient a l'esprit est de jouer chaque coup au hasard. Pas tres efficace, mais le taquin sera pourtant bien resolu un jour.
Sinon, dans le genre plus fiable, tu peux appliquer un parcours en largeur:
http://fr.wikipedia.org/wiki/Algorit...urs_en_largeur
Et dans le genre plus malin, tu peux aussi appliquer A*:
http://fr.wikipedia.org/wiki/Algorithme_A*
L'astuce pour A* est dans le choix de l'heuristique. Pour une config donnee, il suffit de faire la somme des distances de manhattan. Donc pour chaque piece, tu calcules la distance entre sa position courante et sa position finale, puis tu sommes tout.