elly25
Messages postés1Date d'inscriptionjeudi 12 mars 2009StatutMembreDernière intervention12 mars 2009
-
12 mars 2009 à 15:29
Bonjour,
je dois programmer le jeu du taquin qui comprend:
-une classe configuration, correspondant au jeu lorsquel'on déplace une case (fait)
-une classe chemin(type liste) qui regroupe toutes les configurations
-un dictionnaire regroupant toutes les configurations existantes (grace à une table de hachage par exemple):
On suppose disposer d'un dictionnaire D des configurations déjà étudiées. Il peut être représenté par un arbre binaire de recherche, une table de hachage, ou toute autre structure que vous jugerez adéquate.
On suppose disposer d'une file de priorité F dans laquelle on peut entrer des chemins.
Soit I la configuration initiale. L'algorithme de résolution est alors le suivant :
Entrer le chemin réduit à I dans F et entrer I dans D
Tant que F n'est pas vide
Sortir de F le chemin X possédant la plus petite valeur de h
Soit C le dernier élément de X
Si C est l'état final : la solution est X
Sinon, pour tous les successeurs Ci de C faire
Si Ci n'est pas dans D, créer le chemin X'=(X,Ci) (chemin obtenu en ajoutant Ci à la fin de X)
ajouter X' dans F et Ci dans D
Cet algorithme garantit l'obtention d'une solution si elle existe
je vois pas du tout comment faire: il faut faire le dictionnaire D (=table de hachage) à part dans une classe, ou dans la classe chemin?
+, pareil pour F, une classe à part? si oui, comment initialiser le chemin I (= configuration initiale) dans F?
je vois pas du tout, désolé si mes questions sont idiotes mais je suis débutant encore
merci