-
Resolution taquin A*
Bonjour,
Je dois réaliser un solveur du jeu de taquin en utilisant l'algorithme A* et j'avoue avoir beaucoup de mal a démarer, je ne vois pas comment appliquer cet algorithme au jeu du taquin...
A priori d'apres ce que je comprend il faut calculer les déplacements qui seront les moins couteux d'un noeud d'origine du graphe a un noeud destination et que le cout va etre représenter par le nombre d'éléments a déplacer pour arrivé jusqu'au noeud destination.
Mais faut il par exemple prendre en compte plusieur déplacements simultanés ou traiter une par une chaque chaque piece sachant qu'elle devra eventuellement etre déplacée par la suite pour permettre a d'autre piece d'atteindre leur emplacement ?
Si quelq'un a une piste au moins pour débuter je suis preneur parceque la je suis completement bloqué...
-
-
Eh bien, comme souvent, il faut commencer par modéliser mathématiquement le problème à résoudre.
L'algorithme A* est un algorithme de recherche d'un plus court chemin dans un graphe. Il faut donc se poser les questions suivantes :
- Que va représenter un sommet ?
- Que va représenter une arrête ?
Une piste : faire au plus simple.
