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.

[zekabyle]

En effet, je n'y ai jamais joué, c'est pour cela que je pose des questions un peu bête.

J'ai toujours pensé qu'il n'y avait qu'un état final.

[tbc92]

Qu'appelles- tu "Etat final".

Pour moi, l'état final, c'est quand chacune des cases est à la position cible, c.a.d quand le jouerur a résolu le taquin. Et donc oui, il n'y a qu'un Etat final.

[zekabyle]

Exact.
Donc il peut y avoir plusieurs solutions pour arriver à l'état final et donc le parcours comme un arbre permet de déterminer si je comprends bien le plus court chemin avec le nombre de mouvement.

[tbc92]

Des parcours , il y en a effectivement plein. Et des parcours qui conduisent à la situation cible, il y en a effectivement plein.

L'illustration typique, c'est qu'il peut y avoir des boucles : si tu fais un pas vers le nord, puis 1 vers l'Est, un vers le sud et un vers l'ouest, tu es revenu à ton point de départ.
Dans ton algorithme, un des tests pour économiser du temps, ça peut être de vérifier que tu ne reproduis pas une situation déjà vue.
En particulier, après un mouvement 'un pas vers EST', il y a en principe 4 mouvements possibles (Est, Ouest, Nord, Sud), mais le mouvement 'un pas vers Ouest' est idiot, c'est le retour à la position précédente.

[Flodelarab]

Ce n'est pas bien.
Il n'est pas bon d'écrire du code avant même que ton algorithme soit déterminé.
Tu as mis la réalisation avant la conception.


De plus, parler d'arbre est maladroit.
Tu passes d'une position à une autre. Voire à celle dont tu viens !!! Donc, ton "arbre" serait infini.
Le fait qu'il y ait des cycles, ou boucles (retour au même point) fait que c'est toujours un graphe mais pas un arbre.


En gros, à partir d'une position, tu dois choisir un mouvement, déterminer une position, regarder si tu connais la position, archiver, continuer.

Quand tous les mouvements de toutes les positions ont été étudiées, c'est fini pour l'analyse.
Il restera à conclure.

[anapurna]

salut

tu peut appliquer l’algorithme de recherche du chemin minimum a*
et c'est bien un parcours d'arbre ou de graphe sauf que l'on ne met pas en mémoire la totalité des solutions possible
en fait pour le test de déplacement il faut juste vérifier que la case adjacentes est vide

[zekabyle]

J'ai oublié de préciser un point qui m'est encore plus problématique.
Le taquin est cylindrique.
Cela signifie donc plusieurs états finaux ?

[anapurna]

salut

tu n'as qu'un état final qu'il soit cylindrique ,conique , pyramidale ou autre forme bizarroïde le résultat est que tes cellules doivent être dans un certain ordre
une fois cette ordre atteint la recherche est fini

par contre tu as plusieurs possibilité d'atteindre le même but

[tbc92]

Dans le cas du taquin cylindrique, je pense qu'inl y a plusieurs position cibles. Si le taquin est composé de 4 cercles, avec 5 éléments sur chaque cercle, il y aura en fait 5 positions finales.
Pourquoi ça. Dans un taquin classique, si on veut un certain motif ( les case 1 à 5 sur la première rangée , dans l'ordre), alors c'est clair, l'élément n°1 doit être en haut à gauche.
Dans un taquin cylindrique, avec la même contrainte, l'élément n°1 doit être sur la 1ère rangée, et ça suffit. Ce qu'il faut alors, c'est que la position RELATIVE des autres éléments corresponde à la demande (2 à droite de 1, 3 à droite de 2 ... 6 en dessous de 1... etc)
Donc, à moins de trouver une subtilité dans la codification des cases (je ne vois pas comment), je pense qu'il y a plusieurs positions finales.

[Flodelarab]

Le taquin est cylindrique.

Où sont passés nos donuts d'antan ?

[zekabyle]

Le donuts est devenu très taquin

Dans le cas du taquin cylindrique, je pense qu'inl y a plusieurs position cibles. Si le taquin est composé de 4 cercles, avec 5 éléments sur chaque cercle, il y aura en fait 5 positions finales.
Pourquoi ça. Dans un taquin classique, si on veut un certain motif ( les case 1 à 5 sur la première rangée , dans l'ordre), alors c'est clair, l'élément n°1 doit être en haut à gauche.
Dans un taquin cylindrique, avec la même contrainte, l'élément n°1 doit être sur la 1ère rangée, et ça suffit. Ce qu'il faut alors, c'est que la position RELATIVE des autres éléments corresponde à la demande (2 à droite de 1, 3 à droite de 2 ... 6 en dessous de 1... etc)
Donc, à moins de trouver une subtilité dans la codification des cases (je ne vois pas comment), je pense qu'il y a plusieurs positions finales.

Est-ce que ça change donc la manière de déterminer l'heuristique ?

Pour rappel,
Heuristique de recherche
L’heuristique de recherche f(e), associée à un état e, est la somme de deux informations d’heuristique g(e) et h(e) :
f(e) = g(e) + h(e)
g(e) est le coût de la meilleure séquence d’états (solution partielle) connue pour aller de l’état initial à l’état e. Ce coût est le nombre de mouvements pour aller de l’état initial à l’état e.
h(e) est l’estimation du coût de la séquence d’états allant de l’état e à l’état final le plus proche. Ce dernier sera celui dont le nombre de cases mal placées du damier à l’état e est le plus petit. Le coût sera égal à ce nombre de cases mal placées.
f(e) est ainsi une estimation du coût de la meilleure solution (séquence d’états)
passant par e.

tu peut appliquer l’algorithme de recherche du chemin minimum a*
et c'est bien un parcours d'arbre ou de graphe sauf que l'on ne met pas en mémoire la totalité des solutions possible
en fait pour le test de déplacement il faut juste vérifier que la case adjacentes est vide

En effet, c'est vers là que je veux aller mais je n'ai pas encore bien compris cet algorithme.

Je prévois aussi une structure pour stocker la solution.

[tbc92]

La décomposition f(e) = g(e)+h(e) , tout ça , oui, c'est correct.

Mais j'enlève ma casquette d'informaticien, et je mets ma casquette de joueur. Ici, on a plusieurs positions finales, à cause de la forme cylindriques. Compter le nombre de mouvements jusqu'à chacune des positions finales, et garder la valeur minimale, c'est coûteux.

Plutôt que chercher le parcours du début vers la fin, on peut chercher le parcours de la fin vers le début : On a 5 ou 6 positions 'finales', on cherche le dernier mouvement, puis l'avant dernier etc, à chaque fois, on cherche le mouvement qui nous rapproche le plus de la position donnée. On diminue les temps de traitement de façon significative puis qu'on simplifie beaucoup le calcul de la fonction h()

Deuxième astuce. Tu dis que h(e), c'est le nombre de cases mal placées. Oui, on peut dire que c'est une estimation du nombre de mouvements qu'il reste à faire. Mais c'est une estimation très loin de la vraie valeur, c'est en fait un nombre minimal de mouvements. Je te propose cette autre estimation.
A chaque mouvement, on déplace une seule pièce (on permute une pièce et la case vide). On peut donc compter : Pour la pièce X qui est à l'emplacement (a,b) et qui doit aller à l'emplacement (c,d), il faut au minimum dist((a,b),(c,d)) mouvements pour arriver à destination. En prenant la somme des dist((a,b),(c,d)) au lieu du comptage de cases mal placées, on a une meilleure estimation du nombre de mouvements restants. Et ça reste une estimation qui va être inférieure ou égale à la réalité !

Reste à vérifier quand même un truc dans l'énoncé de l'exercice :
On chercher un algorithme qui va vite et qui trouve un chemin (même si ce chemin n'est pas totalement optimal)
Ou on cherche le chemin optimal, même si du coup, il faudra probablement un algorithme qui va chercher plus longtemps.

[Flodelarab]

Le taquin "classique" (non cylindrique) n'a une solution que une fois sur deux.
C'est-à-dire qu'une solution n'existe que dans une position de départ sur deux.
Concrètement, cela veut dire que tu vas lister tous les cas possibles sans espoir, dans le cas défavorable.


D'autre part, utiliser l'algorithme A* pour ce taquin est bizarre car A* est bon quand on a une pré-science du résultat.
Le meilleur chemin pour atteindre une position géographique, par exemple. On se doute qu'il faut se rapprocher de ce but.
Mais ce taquin cylindrique ... En tant qu'être humain, je ne sais pas, a priori, quel procédé rapproche du résultat (multiple).

[anapurna]

salut

il existe une solution pour savoir si la taquin est soluble ou non
regarde sur wikipedia il en parle

le jeu de taquin cylindrique je ne connais pas mais je suppose que l'on part d'une position de départ et que l'on obtient un position final
si vous avez un lien sur la représentation de ce genre de jeux je suis preneur

l'algorithme a* permet d’optimiser le nombre de coup et aussi de réduire le nombre de recherche le choix de la distance est un choix judicieux
même si la distance n'est pas forcement calculé en millimètre mais en colonnes et en lignes
dans le cas d'un taquin cylindrique je vois pas bien les déplacements possible et les combinaisons réalisable