Discussion :

[zekabyle]

Bonjour,

Je dois faire un resolveur de taquin en C++ (sans les classes et objets) et je ne comprends pas comment trouver l'heuristique avec le nombre de cases mal placé et le but. et surtout g et h dans f(e) = g(e) + h(e)
J'ai 2 piles lee et leae pour stocker les états établis et états à établir qui se retrouve dans ma structure Taquin.

Ma structure Etat contient un damier, l'indice de l'état précédent se trouver dans la pile lee, les coordonnées de la case vide, le mouvement, g et h.


Pouvez-vous m'aider pour implémenter en c++ et trouver g et h ?

Il me semble que je dois trouver quelles sont les positions possibles à chaque fois mais je ne vois pas comment trouver ?

Merci

[Flodelarab]

Bonjour

Pouvez-vous m'aider pour implémenter en c++

Non. Par contre, tu peux le faire et nous pouvons commenter.

Pouvez-vous m'aider pour trouver g et h ?

Non. En bon mathématicien, je ne parle pas aux fonctions que je ne connais pas.
Tu voudrais qu'on explicite g et h alors qu'on ne sait même pas ce que c'est. Ni la fonction f, d'ailleurs.

Il me semble que je dois trouver quelles sont les positions possibles à chaque fois mais je ne vois pas comment trouver ?

Le taquin a un trou.
Une des 4 pièces qui sont autour peut combler le trou.
Chaque mouvement possible aboutit à une nouvelle position.
Et de position en position, tu auras listé tous les cas possibles.

Si une solution existe, elle sera dans ta liste.

[zekabyle]

Bonjour,

h est l'heuristique. (nombre de chiffres mal placés)

g est le coût optimal connu d'un état à un final.


Est-ce que dans un taquin, il est possible d'avoir uniquement un état final ou plusieurs états finaux ?

Je pense que la valeur de h se calculerait dans cette fonction ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
inline uint heuristiqueSimple(const Tableau2D &jeu, const Tableau2D &etatFini) {
    uint k = 0;
    for ( uchar i = 0; i < nombre_de_lignes; ++i) {
        for ( uchar j = 0; j < nombre_de_colonnes; ++j ) {
            if ( jeu[i][j] != etatFini[i][j] ) {
                ++k;
            }
        }
    }
    return k;
}

Ce serait en entrée le plateau en cours et le plateau final à atteindre.

[zekabyle]

Il faut que je change car les paramètres d'entrée demandés dans mon exercice sont heuristiqueSimple(Etat &ei) donc voilà dans l'idée :

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
inline uint heuristiqueSimple(Etat &jeu) {
    uint k = 0;
    for ( uchar i = 0; i < nombre_de_lignes; ++i) {
        for ( uchar j = 0; j < nombre_de_colonnes; ++j ) {
            if ( jeu.damier[i][j] != etatFini.damier[i][j] ) {
                ++k;
            }
        }
    }
    return k;
}

Bien sûr, il faudra que je trouve un moyen de faire utiliser etatFini dans la fonction.

Pour info, la structure Etat que j'ai établie :

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
struct Etat
{
	Tableau2D damier;
 
	enum Mouvement { FIXE, NORD, EST, OUEST, SUD };
	Mouvement mouvement;
	int indicelee;
 
	int g;
	int h;
 
	int indicecolonneVide;
	int indiceligneVide;
};

Qu'en dites-vous ?

[anapurna]

salut

la fonction heuristique simple calcul le nombre d’élément mal placé ?
ce qui veut dire qu'il va falloir explorer toutes les solution possible avant de trouver la solution optimal ?

pour résumé simplement si j'ai bien compris

tu as un tableau de Case
Pour chaque case tu as une position final est une position courante qui au final devrais être la même

je verrai bien une structure de case comme celle-ci

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
TCase = RECORD 
  PosFinal      : TPos
  Vide           : Boolean; 
  ...
FIN

pour chaque case tu peut déterminer les différents mouvement possible

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

  MouvPossible = [FIXE, NORD, EST, OUEST, SUD ];

a chaque coup joué il faut actualiser la possibilité de mouvement des cases
la case vide n'est jamais FIXE

en sachant que les mises a jour des cases ne s'applique qu'aux cases directement voisines à celles(vide et non vide) que tu vient de déplacer
posCorant et PosFinal peut être un entier il est possible de linéariser ton tableau
cela veut dire qu'un tableau de 4*4 peut être représenté par une ligne de 16 éléments
les cases doivent être dans le tableau positionnée dans l'ordre de la position courante afin d’accéder aux voisins le plus rapidement

tans que ta poseCourant <> PosFinal Faire un traitement


Ps pour infos les calculs intéressant

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
   IPOS = COL+(LIG-1)*NBCOL
   LIG   =   (IPOS DIV  NBCOL)+1 ;//
   COL  =   IPOS MOD NBCOL;//

[tbc92]

Je pense que tu n'as jamais joué à ce jeu, et donc, tu ne peux pas t'en sortir. Le fait que tu mettes 'FIXE' dans la liste des mouvements, c'est révélateur. J'imagine qu'on peut trouver des jeux de taquin en ligne. Joue 5 ou 6 parties, ça va te permettre d'assimiler les règles du jeu, et l'objectif.
Ensuite, tu pourras réfléchir au sujet.

S'il y a N cases mal placées, alors, une chose est sure, il faudra au moins N mouvements pour arriver à la solution. Mais souvent, il en faudra beaucoup plus. Si tu as 3 cases mal placées à 3 coins du taquin, c'est en gros comme si tu avais toutes les cases mal placées.