je cherche des algoritmes concernant ce casse tête qui consiste à remplire un carré ou un rectangle de n colonnes x m lignes, de (nxm) - 1 jetons, à les melanger, et à les remettre dans l'ordre  
 
Le jeu du taquin, donc  

pas très claire ta phrase...

Ce jeu s'appelle le "jeu du taquin". De là, une recherche sur Gougueule ne devrait pas poser trop de problèmes.

y'a des techniques issues de l'IA pour ça, c'est un exemple typique:
http://www.google.fr/search?q=ia+% [...] r:official

Merci pour l'info, j'avais aucune idée du nom que porte ce casse tête, j'ai lu pousse-pousse aussi.
 
  sur Forum.HardWare.fr
     TAQUIN sous Ada
 
  avec google
     jeu de taquin
     Recherche de solutions optimales au jeu de taquin
     jeu de taquin
     jeu de taquin
     jeu de taquin Je retien ce lien    
     Le taquin
     Résolution de problèmes en Intelligence Artificielle ::=
     Taquin ameliore
     Algorithme utilisé pour la résolution du taquin
 
Voilà, je vais commencer avec ça, j'ai trouvé des sources écritent avec Ada, le pied pour moi .
 
 Il y à pas mal d'Intelligence Artificille apparement aussi IA

 
Mon implémentation du jeu du Taquin avec Ada
 
Cette implémentation du jeu du Taquin ne reflétant pas en réalité le vrai problème posé, j'envisage d'y remédier. Malheuresement mes connaissances en mathématique, algorithmie et structure de donnée sont aujourd'hui insufisantes. Je me lance donc à la recherche d'un spécificateur qui souhaiterait partager le plaisir d'ecrire ou de réecrire une implémentation du jeu du Taquin avec Ada

Mon record : résolution d'un problème de taquin avec 15 carrés (4*4) en moins de 10 secondes à l'optimal (en le moins de mouvement possible), faudrait que je poste le modèle de départ et le modèle final attendu
 
Quelques algorithmes de résolutions : recherche en coût uniforme (pourri), A* (très rapide mais trop gourmand en mémoire), IDA* (trop peu gourmand en mémoire donc trop lent), RBFS (peu gourmand en mémoire mais plus que IDA* donc plus rapide que IDA* donc moins lent mais beaucoup plus lent que A*), SMA* (the best compromis entre mémoire et rapidité. Seul hic : la profondeur de la solution est bornée par la taille maximale d'utilisation de  la mémoire autorisée), et encore d'autres moins connus
 
RQ : tous ces algo garantissent l'optimalité et la complétude (si suffisamment de mémoire (pour A* et SMA*) ou si vous êtes patients (IDA* et RBFS))
 
VERDICT : algorithme conseillé : SMA* : gère mieux la mémoire que A* tout en étant légèrement plus lent.
Voilà pour résumé de longs chapitres
 
EDIT : j'ai le code java pour A*, IDA* si tu veux
 
EDIT 2 : partir sur un algo de permutation est du sucide ! : après un petit calcul mathématique, pas moins 9! permutations possibles pour un plateau de 3*3 et 16! pour un plateau de 4*4 (l'énumération dans ce dernier cas devient impossible, seules les recherches informées peuvent encore trouver un e solution parfois)
 
RQ important : certain problème de taquin N'ONT PAS DE SOLUTION => une mauvaise implémentation ferait boucler indéfiniment le programme !

Pour information, voici quelques uns de mes résultats obtenus avec A* ;
algorithme le plus rapide que je connaisse pour résoudre le problème du
taquin. Voici ci-dessous 4 problèmes différents définis par un tirage aléatoire
du plateau de départ.
 
 
PLATEAU D'ENTREE
----------------
 
Cas 1 :
 

 
Cas 2 :
 

 
Cas 3 :
 

 
Cas 4 :
 

 
PLATEAU DE SORTIE
-----------------
 
Dans tous les cas, je suppose la solution d'arrivée être la suivante :
 

 
RQ : Pour le cas 4, le plateau solution défini est établi selon la même logique.
 
Mes Résultats
-------------
 
Cas1 :
 
Solution optimale : 44 mouvements (19192 plateaux générés et 12605 plateaux
evalués par l'heuristique).
Temps de résolution : 0.366 seconde
 
Cas2 :
 
Solution optimale : 49 mouvements (681814 plateaux générés et 440373 plateaux
evalués par l'heuristique).
Temps de résolution : 3.125 secondes
 
Cas3 :
 
Solution optimale : 47 mouvements (2005778 plateaux générés et 1282227 plateaux
evalués par l'heuristique).
Temps de résolution : 9.975 secondes
 
Cas4 :
 
Pas de solution (problème insoluble).
 
Commentaires
------------
 
*) Alors déjà, on voit qu'avec le cas 4, il se peut que le problème soit insoluble.
Alors pour vous prouver que ce n'est pas mon algo qui cafouille, voici un
exemple que vous pouvez résoudre à la main et qui n'a pas de solution
 

 
Et son plateau de solution considéré (et inatteignable) :
 

 
*) Ensuite on voit que la résolution avec A* est très rapide. Le gros problème
de cet algorithme est que soit il résoud le problème très rapidement à l'optimal
soit il dépasse la taille mémoire du pc car trop gourmand. On voit donc bien que
cet algo offre un très mauvais équilibre entre utilisation mémoire et
utilisation CPU.
 
*) Pour le cas 3 par exemple, j'ai été obligé d'augmenter la taille du tas
maximal autorisé par la JVM (-Xmx128m au lieu de -Xmx64m par défaut)
 
*) Par contre on voit bien l'efficacité de l'aspect "Branch and Bound" de
l'algorithme. Une énumération complète d'un plateau de taille 4*4 admet pas
moins de 16! configurations possibles (~= 2.10^13) ce qui non énumérable car
requiert trop de temps. Mais n'oublions pas qu'il s'agit d'une borne max car
toutes les configurations possibles ne sont pas forcément atteignables (cf.
point ci-dessus). Cet aspect-ci montre toute sa splendeur dans le cas 1 (très
peu de plateaux générés).
 
 
*) Programme réalisé en Java 1.5. Benchs réalisés sur ma config Athlon64 3200+
avec 2Go de RAM. Si y'en a qui arrive à résoudre plus vite le problème, je suis
preneur. Le concours est ouvert .

En attendant de maitriser  l'algorithme A*, j'ai fait un truc avec un arbre n-aire. je construit l'arbre jusqu'a trouver la solution, en eliminant quelques doublons, eventuellement
 
l'algo que j'ai trouvé pour remplire l'arbre    
 

while not Fini loop
        while A_Un_Fils(Dans) loop
               Passer_Au_Suivant(Dans);
        end loop;
        ---------------------
           ajouter les noeuds suivants
        ---------------------
         Passer_Au_Parent(Dans);
            while not A_La_Racine(Dans) loop
               while A_Un_Frere(Dans) loop
     
                  Passer_Frere_Suivant(Dans);
                  while A_Un_Fils(Dans) loop
                     Passer_Au_Suivant(Dans);
                  end loop;
                ---------------------
                   ajouter les noeuds suivant
                 ---------------------
                  Passer_Au_Parent(Dans);
     
               end loop;
             Passer_Au_Parent(Dans);
          end loop;
      end loop;

 
je suis qu'un amateur  
a parament vous parlez de performance ; mon algo met 5 minutes a trouver un matrice 3x3,    
en affichant les matrices quant meme,  sur un pc
je vais lancer un matrice 4x4 pendant que je dors
demain j'implementerais la suppression des doublons, je ferais un compraraison,
 
j'aimerai bien tester l'algorithme A* mais je comprend rien aux math, bref    
 
   

je suis en traine de lire Giz
 
S'il est indeniable que mon algo n'est pas adapté a des matrices superieur 3x3 sur de petits systemes,
il doit avoir l'avantage de trouver la solution. c'est ce que je lui demande.
Je vais me pencher sur cette nuance, solution est solution calculable par d'autres algorithmes
 comme A* ou SMA* qui d'apres tes dires Giz, ne trouve pas toutes les solutions. Regrétable. Engoissant même.
T'ant qu'a faire, pour continuer mon travail, j'opterai pour pour le meilleur algo, donc SMA*.
Mais s'il ne trouve pas toute les solutions, ce n'est pas une solution en soit.
Si je connaissai un peu mieu les math je pourer affirmer que mon algo est perfectible.
 
n'existe t-il pas des solutions comme avec un Rubic's cub, que l'on pourait ajouter au methodes permutter_{up,down,left,rigtht}
serait-il possible d'integrer les solutions avec au moins une vrai qui calcule coute que coute la solution  
 
j'aimerai bien connaitre le nombre de matrices genérées dans mon cas pour comparer ; je vais l'implementer.
 
merci Giz,
pour le code, je me taperai bien l'algo A* en Java, tu peut m'ecrire à jovalise@gmail.com,
je me mettrai au Java, j'implementerai une version Ada, j'essairai de l'intégrer a mon algo.
 
Le concourt sera ouvert sur une specification precise ?
 
-- doit touver la solution si elle existe ;
-- doit prendre une matrice NxM avec un element vide en position initiale en K,L, N,M,K,L vairiable.
 
pour l'instant pour une matrice 3x3 bien melangée il me faut 5 minutes  150 Mo ram sur un P4 2.4
et j'obtien soit un segment fault avec une matrice 4x4, soit un arret du programme pour defaut de memoire,
j'arrive a manger 2,5 de memoire quand même,
 
le probleme est de taille, le defit est relevé
tres interressant comme cas d'etude
 
Merci Giz, encore    
 
 

Mon algo : 5_000_000 de matrices   , pour un matrice 3x3 bien melangée, en 5 minutes

avec une recherche de doublons dans les noeuds parents, plus que 70_000 matrices générées pour une matrice 3x3, resolut en plusieur minutes, quand même.

jovalise plusieurs points :
 
1) Moi je ne m'intéresse qu'à la solution optimale du problème. Car des solutions quelconques il en existe une infinité à partir du moment où il en existe au moins une ! .
 
2) Les problèmes insolubles, comme je l'ai cité, est un problème réel...ça ne vient pas de l'algorithme. Essaie de résoudre à la main l'exemple de 2*2 que j'ai donné ... c'est pas possible.
 
3) avant de te mettre à SMA*, essai A* sinon tu risques d'être perdu car SMA* est une amélioration de A* niveau mémoire.

Bon, j'avous, mon algo n'est pas optimal  ,

Re bonjour à tous,    
 
j'ai cherché et j'ai trouvé quelques bonnes pages, sur l'algorithme dit de Dijkstra et sur l'algorithme A*.
Je me demande en quoi les deux diffèrent ?. N'ayant pas encore les connaissances pour le determiner moi même je pose la question ici. C'est peut-etre pas tres important pour le moment vue que je comprend rien, ni à l'un, ni à l'autre.
 
Je me demande aussi si l'algorithme A*, adapté au problème de la résolution du jeu du Taquin, repond à la specification suivante :
 
Resoudre une matrice NxM avec un vide placé en k,l  
 
Un vide placé en milieu de matrice ne pose-t-il pas probleme ?

Dijsktra appliqué à la résolution du taquin correspond à l'algorithme de recherche en coût uniforme. En clair, tu estimes seulement la distance entre ton point de départ et l'état sur lequel tu es. Par exemple, tu pars d'un plateau de départ et tu arrives au bout de trois mouvements sur un plateau qui a un cout de trois (le nombre de mouvements effectué entre ton état de départ et l'état actuel). Le problème c'est que ton estimation peut être amélioré autrement dit, toi ce qui t'interesse c'est le cout que tu as en comptant à partir de l'état de départ (cout uniforme donc) (ben ouai plus tu fais de mouvements et plus la solution vers laquelle tu te dirige est médiocre) ET le cout qui te reste à faire (le nombre de mouvements à faire AU MINIMUM pour atteindre l'état final) pour aller au plateau solution d'arrivée. Ce dernier coût est estimé par une heuristique qui est donc admissible (admissible <=> AU MINIMUM). Cette heuristique transforme donc la recherche en coût uniforme en une recherche type A*. Maintenant tu auras un état évalué par 2 coûts ! tu es donc plus précis sur l'évaluation d'un plateau et donc tu pourras couper des branches de l'arbre car ce n'est pas forcé qu'un état ayant un coût uniforme faible ait un coût heuristique faible et donc dans ce cas, un plateau avec un coût heuristique bien plus faible et un coût uniforme à peine plus fort peut être de meilleur qualité (et donc appartient à un meilleur chemin). Dorénavant, à chaque plateau tu sommeras donc ces 2 coûts pour évaluer un plateau du jeu. A partir de la, tu constitues un arbre de solution que tu déploieras intelligemment l'arbre c'est à dire en fonction des coûts de chaque plateau. Plus le coût est bas et plus le plateau est à privilégier pour créer ses fils ... qui ont plus de chance de mener au plateau solution (et donc au chemin solution).
Ce qu'il te reste à faire c'est de trouver une heuristique ADMISSIBLE c'est à dire, étant donné un plateau non solution, combien de mouvements AU MINIMUM reste-t-il à faire pour arriver au plateau solution.
Voilà l'idée de A*.

Merci Giz,  
Ce que j'ai compris, à peut près.
je reformule ...  
 1 L'algorithme A* est une heuristique qui donne un coût/une distance entre deux etats ! et c'est tout ! Ou génère t'il en même temps les differents etats dont il mesure l'éloignement/rapprochement ? ... j'usqu'a trouver la solution ; une solution complete au jeu du taquin quoi ?  
 2 Ce coût est une somme du nombre de mouvements effectué pour arriver à une etat intermediaire et du nombre de mouvement restant à effectuer pour arriver à un etat final ou un autre etat intermediaire !  
 
, les contraintes de deplacement/mouvement du Jeu du taquin sont-ils connuent de l'algorithme A*
 
Et pour mon problème de vide en milieu de matrice ? qu'en penses-tu ?
 
 
 
 

j'ai oublié les questions essencielles qui peuvent me facilliter la compréhension du problème
 
Quelles sont les données que prend et retourne l'algorithme A* ?l

 
L'algorithme A* C'EST COMME la recherche en coût uniforme SAUF qu'il considère EN PLUS un deuxième coût sur l'évaluation d'un plateau : le coût qu'il y a AU MINIMUM pour arriver à l'état solution (en nombre de mouvements).
A* te permettra donc de trouver la solution optimale au problème de manière plus performante car la recherche est plus informée. A* est un algorithme de recherche "de plus court chemin" (ce qui est notre cas avec le taquin, où l'on cherche la solution de chemin le plus court : le moins de mouvements possible), mais en général on emploi de terme dans les graphes ce serait plus "recherche de chemin optimal" (pathfinding algorithm). Le coût défini par A* est le coût de l'état initial à l'état courant + le coût ESTIME de l'état courant à l'état final (tu fais la somme des 2 pour obtenir un unique coût associé à chaque plateau).
Les ontraintes de déplacement sont à définir par toi ! lorsque A* demande les succeseurs, ces à toi de lui fournir les bons.
@ demain ...

re Bonjour à tout le monde    
jC'est le pseudo-code de l'algoritme A Star que je prefaire dans ceux que j'ai touvés pour l'instant

 
je me demande de quel(s) pionts ils parlent quant ils invoquent les successeurs de n,
et même n, je me demande de quel n ils parlent quant il invoque n dans les ouverts tel que f(n) est minimum
 
je ne sais pas non plus de quoi ils parlent quant ils invoque g(n) et coût(n,s)
 
je trouve que ça fait terriblement defaut,
 
[i]c'est peut-etre du au fait que ces "valeur" sont indépendentes de l'algorithme A Star
 

J'ai commencé a reformuler le speudo-code ci-dessu, mais c'est pas top
 

-----------------------------------------------------------------------
   --               Resolution du Jeu du Taquin                         --
   -----------------------------------------------------------------------
   procedure Astar (Dans : in out T_Jeu_Du_Taquin) is
   -----------------------------------------------------------------------
   --                      Algorithme A* ou Astar                       --
   -----------------------------------------------------------------------
      Succes : Boolean := Boolean'Value("FALSE" );
      Noeud_Courant : T_Place_Ensemble;
      Nouveau_Successeur : T_Matrice;
   begin
      ajouter(Ensemble => Dans.Ouvert,Avec => Dans.Matrice_melangee);
      Vider(Ensemble => Dans.Ferme);
      while not Est_Vide(Dans.Ouvert) and not Succes loop
         Noeud_courantt := L_Element_Min(Ensemble => Dans.Ouvert).all;
         -- la, va faloire determiner L_Element_Min
         if -- la j'ai pas le test je comprend plus -- then
           Succes := Boolean'Value("TRUE" );
         else
            Supprimer_noeud(Ensemble => Dans.Ouvert,Avec => Noeud_courant.id);
            ajouter(Ensemble => Dans.Fermer,Nouveau => Noeud_Courant.matrice);
            for I in -- ensemble -- loop
                         -- la je pense que l'algo doit varier en fonction de sont utilisation
 
               if not Esiste(Ensemble => Dans.Ouvert,L_Element => Nouveau_Successeur) and
                 not Esiste(Ensemble => Dans.fermer,L_Element => Nouveau_Successeur) then
                  -- la y a un chmilblic -- on vient de supprimer Noeud_courant de Ouvert est on doit lui ajouter un fils, c'es
t louche
                  Ajouter(Ensemble => Dans.ferme, Avec =>  Nouveau_Successeur);
                  g(s) := g(n) + coût(n,s);  -- la je sais pas quoi faire de cette ligne
               elsif (g(s) > g(n) + coût(n,s)) then -- la pareil
                  Ajouter(Ensemble => Dans.Fermer, Avec => Nouveau_Successeur);
                  g(s) = g(n) + coût(n,s);
                  if Existe(Ensemble => Dans.Ferme, L_Element => Nouveau_success)s se trouve dans fermés) then
                     -- la, je comprend plus non plus, on vient de rajouter Nouveau_successeur a ferme et on test s'il y est ?
                     -- le reste, c'est pire donc
                     fermés  = fermés  - S;
                     ouverts = ouverts + S;
                     --
                     -- je doit me planter quelque part !!!!!
                  end if;
               end if;
            end loop;
 
         end if;
 
      end loop;
 
   -----------------------------------------------------------------------
   --                     Fin algorithme A* ou Astar                    --
   -----------------------------------------------------------------------
 
   end Astar;

A la ligne 17 on doit pouvoir mettre
 

if Sont_Egales(Gauche => Noeud_Courant.Matrice, Droite => Dans.Matrice_Initiale) then

Pour la ligne 22, j'ai un tableau "mouvement" de fonction qui renvoit l''element voisin si un deplacement vert cet element est possible, zero si non.
 
on,  je peut donc mettre ligne 22

for I in mouvement loop

il faut alors rejouter ce test

if (Mouvement(I) (Absisse(Noeud_Courant.Matrice ,0),       -- si mouvement(i) /= 0
                      Ordonnee(Noeud_Courant.Matrice ,0),
                      Noeud_Courant.Matrice) /= 0) then

 
générer la nouvelle matrice

Nouveau_Successeur := Noeud_Courant.Matrice;
          Permuter(Nouveau_Successeur,
               Mouvement(I)
               (Absisse(Nouveau_Successeur ,0),       -- si mouvement(i) /= 0
                Ordonnee(Nouveau_Successeur ,0),
                Nouveau_Successeur);

 
ce qui donne pour le moment
 

-----------------------------------------------------------------------
   --               Resolution du Jeu du Taquin                         --
   -----------------------------------------------------------------------
   procedure Astar (Dans : in out T_Jeu_Du_Taquin) is
   -----------------------------------------------------------------------
   --                      Algorithme A* ou Astar                       --
   -----------------------------------------------------------------------
      Succes : Boolean := Boolean'Value("FALSE" );
      Noeud_Courant : T_Place_Ensemble;
      Nouveau_Successeur : T_Matrice;
   begin
      ajouter(Ensemble => Dans.Ouvert,Avec => Dans.Matrice_melangee);
      Vider(Ensemble => Dans.Ferme);
      while not Est_Vide(Dans.Ouvert) and not Succes loop
         Noeud_courantt := L_Element_Min(Ensemble => Dans.Ouvert).all;
         if -- la j'ai pas le test je comprend plus -- then
           Succes := Boolean'Value("TRUE" );
         else
            Supprimer_noeud(Ensemble => Dans.Ouvert,Avec => Noeud_courant.id);
            ajouter(Ensemble => Dans.Fermer,Nouveau => Noeud_Courant.matrice);
            for I in Mouvement'range loop
               if (Mouvement(I)
                  (Absisse(Noeud_Courant.Matrice ,0),       -- si mouvement(i) /= 0
                   Ordonnee(Noeud_Courant.Matrice ,0),
                   Noeud_Courant.Matrice) /= 0) then
 
                  -- generer la nouvelle matrice
                  Nouveau_Successeur := Noeud_Courant.Matrice;
                  Permuter(Nouveau_Successeur,
                           Mouvement(I)
                           (Absisse(Nouveau_Successeur ,0),       -- si mouvement(i) /= 0
                            Ordonnee(Nouveau_Successeur ,0),
                            Nouveau_Successeur);
 
 
 
 
                  -- la je pense que l'algo doit varier en fonction de sont utilisation
 
                  if not Esiste(Ensemble => Dans.Ouvert,L_Element => Nouveau_Successeur) and
                    not Esiste(Ensemble => Dans.fermer,L_Element => Nouveau_Successeur) then
                     -- la y a un chmilblic -- on vient de supprimer Noeud_courant de Ouvert est on doit lui ajouter un fils, c'es
t louche
                     Ajouter(Ensemble => Dans.ferme, Avec =>  Nouveau_Successeur);
                     g(s) := g(n) + coût(n,s);  -- la je sais pas quoi faire de cette ligne
                  elsif (g(s) > g(n) + coût(n,s)) then -- la pareil
                     Ajouter(Ensemble => Dans.Fermer, Avec => Nouveau_Successeur);
                     g(s) = g(n) + coût(n,s);
                     if Existe(Ensemble => Dans.Ferme, L_Element => Nouveau_success)s se trouve dans fermés) then
                        -- la, je comprend plus non plus, on vient de rajouter Nouveau_successeur a ferme et on test s'il y est ?
                        -- le reste, c'est pire donc
                        fermés  = fermés  - S;
                        ouverts = ouverts + S;
                        --
                        -- je doit me planter quelque part !!!!!
                     end if;
                  end if;
               end if;
            end loop;
 
         end if;
 
      end loop;
 
   -----------------------------------------------------------------------
   --                     Fin algorithme A* ou Astar                    --
   -----------------------------------------------------------------------
 
   end Astar;

 
mais ça va pas en fait !!!! le nouveau test est mal placé a mon avis
 
il doit faloire le placer plus haut, accompagné de la boucle ainsi

-----------------------------------------------------------------------
   --               Resolution du Jeu du Taquin                         --
   -----------------------------------------------------------------------
   procedure Astar (Dans : in out T_Jeu_Du_Taquin) is
   -----------------------------------------------------------------------
   --                      Algorithme A* ou Astar                       --
   -----------------------------------------------------------------------
      Succes : Boolean := Boolean'Value("FALSE" );
      Noeud_Courant : T_Place_Ensemble;
      Nouveau_Successeur : T_Matrice;
   begin
      ajouter(Ensemble => Dans.Ouvert,Avec => Dans.Matrice_melangee);
      Vider(Ensemble => Dans.Ferme);
      while not Est_Vide(Dans.Ouvert) and not Succes loop
         for I in Mouvement'range loop
            if (Mouvement(I)
                (Absisse(Noeud_Courant.Matrice ,0),       -- si mouvement(i) /= 0
                 Ordonnee(Noeud_Courant.Matrice ,0),
                 Noeud_Courant.Matrice) /= 0) then
 
               Noeud_courant := L_Element_Min(Ensemble => Dans.Ouvert).all;
               if -- la j'ai pas le test je comprend plus -- then
                 Succes := Boolean'Value("TRUE" );
               else
                  Supprimer_noeud(Ensemble => Dans.Ouvert,Avec => Noeud_courant.id);
                  ajouter(Ensemble => Dans.Fermer,Nouveau => Noeud_Courant.matrice);
 
                  -- generer la nouvelle matrice
                  Nouveau_Successeur := Noeud_Courant.Matrice;
                  Permuter(Nouveau_Successeur,
                           Mouvement(I)
                           (Absisse(Nouveau_Successeur ,0),       -- si mouvement(i) /= 0
                            Ordonnee(Nouveau_Successeur ,0),
                            Nouveau_Successeur);
 
 
 
 
                  -- la je pense que l'algo doit varier en fonction de sont utilisation
 
                  if not Esiste(Ensemble => Dans.Ouvert,L_Element => Nouveau_Successeur) and
                    not Esiste(Ensemble => Dans.fermer,L_Element => Nouveau_Successeur) then
                     -- la y a un chmilblic -- on vient de supprimer Noeud_courant de Ouvert est on doit lui ajouter un fils, c'es
t louche
                     Ajouter(Ensemble => Dans.ferme, Avec =>  Nouveau_Successeur);
                     g(s) := g(n) + coût(n,s);  -- la je sais pas quoi faire de cette ligne
                  elsif (g(s) > g(n) + coût(n,s)) then -- la pareil
                     Ajouter(Ensemble => Dans.Fermer, Avec => Nouveau_Successeur);
                     g(s) = g(n) + coût(n,s);
                     if Existe(Ensemble => Dans.Ferme, L_Element => Nouveau_success)s se trouve dans fermés) then
                        -- la, je comprend plus non plus, on vient de rajouter Nouveau_successeur a ferme et on test s'il y est ?
                        -- le reste, c'est pire donc
                        fermés  = fermés  - S;
                        ouverts = ouverts + S;
                        --
                        -- je doit me planter quelque part !!!!!
                     end if;
                  end if;
               end if
            end if;;
         end loop;
      end loop;
 
   -----------------------------------------------------------------------
   --                     Fin algorithme A* ou Astar                    --
   -----------------------------------------------------------------------

 
comme ça l'algorithme A* et intégré a la boucle qui fournit les successeurs
 
On  pourait s'arranger pour conserver l'algorithme original en construisant, avant la boucle for, une liste des sussesseurs de Noeud_Courant mais bon, ça doit revenir au même. je trouve que c'est plus lisible ainsi !  

 
j'ai oublié de dire que le code ci-dessu est écrit avec le langage Ada

Je ne sais pas si j'ai juste jusqu'ici, mais je voudrais passer au problème des distances.
j'ai presque pas d'idées du tout,    
j'ai jeté un coup d'oeuil à un prog que j'ai trouvé sur le net, ecrit avec Ada mais l'implementation ne me plaie pas, elle est pleine de constante ce basant sur le fait que le Taquin fait toujours 3x3.    
le peut d'idées que j'ai sont des invention de toute pieces pour lequelles il serait hazardeu de vouloire demontrer leur verité mathematique
 
mais y a bien ça :
 
g(n) = somme des nombres de coup pour palcer chaque tuile a ça place courante depuit l'etat initiale;
cout(s,n) = somme des nombres de coup pour placer chaque tuile a ça place finale depuit  l'etat courant;  
 
evidement, je peut vous assurer qu'en ecrivant ça j'ai une vue tres simple de sont ça formulation, pour moi en tout cas
parce que je fait abstraction du chemin réel que doit prendre une tuile pour prendre une place sans trop deranger les tuiles en place
c'est pour ça que je pense que c'est pas juste
 
en parlant de chemins, il doit bien exister des combinaisons, comme avec un Rubic's Cube, que l'on pourait ajouter aux methodes de mouvement up, down, left, right
c'est un autre sujet, mais lachez vous si vous avez des idées
 

Voila les deux fonction Distance_A_L_Initiale et Distance_A_La_Terminale
Ce sont les même en faite il y en a une de trop a priorie, c'est pas normal    

Function Distance_A_L_initiale(Courante : T_Matrice ; initiale : T_Matrice) return natural is
         Somme : Natural := 0;
 
      begin
         for I in 0..N*M-1 loop
            Somme := Somme + (abs(Absisse(Courante,I) - Absisse(Source,I)) +
                              abs(ordonnee(Courante,I) - ordonnee(Source,I)));
         end loop;
         Retrun Somme;
      end Distance_A_L_initiale;

Function Distance_A_La_terminale(Courante : T_Matrice ; terminale : T_Matrice) return natural is
         Somme : Natural := 0;
 
      begin
         for I in 0..N*M-1 loop
            Somme := Somme + (abs(Absisse(Courante,I) - Absisse(terminale,I)) +
                              abs(ordonnee(Courante,I) - ordonnee(terminale,I)));
         end loop;
         Retrun Somme;
      end Distance_A_La_terminale;

 
mais Distance_La_Terminale colle pas avec Coût(s,n),
Distance_La_Terminale prend Nouveau_successeur, ok, et Matrice_Initiale pas Noeud_Courant.Matrice
 
je spécule, je spécule  
 

j'ai oublié une adition dans Distance_A_La_Terminale

Function Distance_A_La_terminale(Courante : T_Matrice ; Initiale,Terminale : T_Matrice) return natural is
      Somme : Natural := 0;
 
   begin
      for I in 0..N*M-1 loop
         Somme := Somme + (abs(Absisse(Courante,I) - Absisse(terminale,I)) +
                           abs(ordonnee(Courante,I) - ordonnee(terminale,I)));
         Somme := Somme + Distance_A_L_Initiale(Courante,Initiale);
      end loop;
      Return Somme;
   end Distance_A_La_terminale;

Bon, voila mon implémentation avec Ada pour le moment, mais ça marche pas alors j'ai commencé a mettre des Put_Line("TOTO" ); partout pour voire ou ça bloque    
 

procedure Astar (Dans : in out T_Jeu_Du_Taquin) is
   -----------------------------------------------------------------------
   --                      Algorithme A* ou Astar                       --
   -----------------------------------------------------------------------
      Succes : Boolean := Boolean'Value("FALSE" );
      Noeud_Courant : T_Place_Ensemble;
      Nouveau_Successeur : T_Matrice;
   ------------------------------------------------------------------------
   --   la fonction qui retourn l'element avec la distance minimale      --
   function L_Element_Min (Ensemble : T_Ensemble) Return T_Place_Ensemble is
      Courant : T_Ptr_Place_ensemble := Ensemble.Tete;
      Element_Min : T_Ptr_Place_Ensemble := Ensemble.Tete;
   begin
      while Ensemble.Courant /= null loop
         if Distance_A_La_Terminale(Ensemble.Courant.Matrice,Dans.Matrice_Melangee,Dans.Matrice_Initiale) +
           Distance_A_L_initiale(Ensemble.Courant.Matrice,Dans.Matrice_melangee) <
           Distance_A_La_Terminale(Element_Min.Matrice,Dans.Matrice_Melangee,Dans.Matrice_Initiale) +
           Distance_A_L_initiale(Element_Min.Matrice,Dans.Matrice_melangee) then
            Element_Min := Ensemble.Courant;
         end if;
         Courant := Courant.Suivant;
      end loop;
      return Element_Min.all;
   end L_Element_Min;
 
 
 
   task Gadget_Affichage is
      entry Maj (compteur : Positive;Matrice : T_matrice);
   end;
   task body Gadget_Affichage is
      Local_Compteur : Positive;
   begin
 
      loop
 
         accept Maj(Compteur : Positive;Matrice : T_matrice) do
            Local_Compteur := Compteur;
            Clear_return := System("clear" & Ascii.Nul);
            Afficher(Matrice);
            Put("Compteur de matrices : " & Integer'Image(Local_Compteur));
         end Maj;
      end loop;
   end Gadget_Affichage;
 
   Count : Natural := 0; -- Nombre de matrices generees
   begin
      Put_Line("DEBUT" );
      ajouter(Ensemble => Dans.Ouvert,Avec => Dans.Matrice_melangee);
      Vider(Ensemble => Dans.Ferme);
      while not Est_Vide(Dans.Ouvert) and not Succes loop
         Put_Line("TOTO-0" );
         for I in solution'range loop
            Put_Line("TOTO-0-1" );
            Noeud_courant := L_Element_Min(Ensemble => Dans.Ouvert);
            if (solution(I)
                (Absisse(Noeud_Courant.Matrice ,0),       -- si mouvement(i) /= 0
                 Ordonnee(Noeud_Courant.Matrice ,0),
                 Noeud_Courant.Matrice) /= 0) then
               Put_Line("TOTO-1" );
 
               if Sont_Egales(Gauche => Noeud_Courant.Matrice, Droit => Dans.Matrice_Initiale) then
                 Succes := Boolean'Value("TRUE" );
               else
                  Put_Line("TOTO-2" );
                  Supprimer_noeud(Ensemble => Dans.Ouvert,element => Noeud_courant.matrice);
                  Put_Line("TOTO-2-1" );
                  ajouter(Ensemble => Dans.Ferme, avec => Noeud_Courant.matrice);
                  Put_Line("TOTO-2-2" );
                  -- generer la nouvelle matrice
                  Nouveau_Successeur := Noeud_Courant.Matrice;
                  Put_Line("TOTO-2-3" );
                  Permuter(Nouveau_Successeur,
                           solution(I)
                           (Absisse(Nouveau_Successeur ,0),       -- si mouvement(i) /= 0
                            Ordonnee(Nouveau_Successeur ,0),
                            Nouveau_Successeur));
                  -- la je pense que l'algo doit varier en fonction de sont utilisation
                  Put_Line("TOTO-2-4" );
                  if not Existe(Ensemble => Dans.Ouvert,L_Element => Nouveau_Successeur) and
                    not Existe(Ensemble => Dans.ferme,L_Element => Nouveau_Successeur) then
                     Put_Line("TOTO-3-1" );
                     -- la y a un chmilblic -- on vient de supprimer Noeud_courant de Ouvert est on doit lui ajouter un fils, c'est l
ouche
                     Ajouter(Ensemble => Dans.ferme, Avec =>  Nouveau_Successeur);
                  elsif Distance_A_L_initiale(Nouveau_Successeur,Dans.Matrice_Melangee) > Distance_A_L_initiale(Nouveau_Successeur,Da
ns.Matrice_Melangee) + Distance_A_La_terminale(Nouveau_Successeur,Dans.Matrice_Melangee,Dans.Matrice_initiale) then
                     Put_Line("TOTO-3-2" );
                     Ajouter(Ensemble => Dans.Ferme, avec => Nouveau_Successeur);
                     if Existe(Ensemble => Dans.Ferme, L_Element => Nouveau_successeur) then
                        Put_Line("TOTO-4" );
                        -- la, je comprend plus non plus, on vient de rajouter Nouveau_successeur a ferme et on test s'il y est ?
                        -- le reste, c'est pire donc
                        Supprimer_noeud(Ensemble => Dans.Ferme, Element => Nouveau_Successeur);
                        Ajouter(Ensemble => Dans.Ouvert, Avec => Nouveau_Successeur);
                        --
                        -- je doit me planter quelque part !!!!!
                     end if;
                  end if;
               end if;
               Count := Count + 1;
               Gadget_Affichage.Maj(Count,Nouveau_successeur);
            end if;
         end loop;
      end loop;
   -----------------------------------------------------------------------
   --                     Fin algorithme A* ou Astar                    --
   -----------------------------------------------------------------------
   end Astar;

 
Gadget_Affichage c'est pour afficher des infos pendant le resolution

Après avoir corrigé mes petites erreurs, j'arrive a générer 8 matrices, mais ça plante encore.
 
J'ai besoin d'aide pour reprendre l'essenciel de l'algorithme A star
 
Merci

 Je comprend pas quant il disent : père(s) = n :
 
edit : Ils sont pas claire cest algos, y en à pas deux pareils,  

Excusez moi j'ai pas posté au bon endroit, sorry
 
j'ai un problème avec cette procedure, qui plante sur le Put_Line("TOTO-11" ); ligne 7 et courant n'est pas null à la ligne 8  
 
 

------------------------------------------------------------------------
   --   la fonction qui retourn l'element avec la distance minimale      --
   --   Methode : parcourt total de la liste
 
   function L_Element_Min (Ensemble : T_Ensemble) Return T_Place_Ensemble is
      Courant : T_Ptr_Place_ensemble := Ensemble.Tete;
      Element_Min : T_Ptr_Place_Ensemble := Ensemble.Tete;
   begin
      Put_Line("TOTO-11" );
      if Courant = null then
         raise Program_Error;
      end if;
      while Courant.suivant /= null loop
         Put_Line("TOTO-11-1" );
         if (Distance_A_La_Terminale(Courant.Matrice,Dans.Matrice_melangee,Dans.Matrice_Initiale) +
           Distance_A_L_initiale(Courant.Matrice,Dans.Matrice_melangee)) <
           (Distance_A_La_Terminale(Element_Min.Matrice,Dans.Matrice_Melangee,Dans.Matrice_Initiale) +
           Distance_A_L_initiale(Element_Min.Matrice,Dans.Matrice_melangee)) then
            Put_Line("TOTO-12" );
            Element_Min := Courant;
         end if;
         Put_Line("TOTO-13" );
         Courant := Courant.Suivant;
      end loop;
      Put_Line("TOTO-14" );
      return Element_Min.all;
   end L_Element_Min;

Merci pour votre aide

Voila, j'ai corrigé toute mes erreurs de base, ça tourne, mais en faite ça tourne pas,
J'ai lancé un matrice 3x3, et ça tourne dans le vide ... Un probleme de distance au moins
 
merci à ceux qui planchent
 
je vais mettre les sources de Taquin_14 à disposition ICI

je me suis encore trompé de topic, c'est ici qu'il faut que je poste ça
 
 
Comme aujourd'hui c'est vendredi, je fait le point
 
1 : dans le pseudo-code que j'utilise pour implémenter l'algorithme A*, qui se trouve un peut plus haut dans cette page,
      je ne comprend pas pere(s) = n, j'ai bien une idée, mais pour l'instant elle n'apporte rien.
 
2 : j'ai implémenté deux fonction Distance_A_Linitiale et Distance_A_La_Terminale qui calculent les distances et qui sont les même en fait
     ça m'étonnerai qu'elles soient justes, je les ai inventées en toute simplicité
 
3 : la fonction L_Element_min dépendant directement de ces fonction de calcul de distance,
     L_Element min doit etre faussé.
 
4 : l'algorithme tourne un peut, c'est à dire qu'il lui arrive de trouver une solution (pas optimale).
      Quand bien même, la liste des permutations obtenue dans l'ensemble fermé n'est pas continue,
      c'est à dire que je permute des element non contiguë dan la matrice
      Normal me dirais-vous vue les trois premiers points
 
Ma fonction de calcul de distance, retourne Somme

for I in 0..N*M-1 loop
         Somme := Somme + ((abs(Absisse(Courante,I) - Absisse(terminale,I)) +
                           abs(ordonnee(Courante,I) - ordonnee(terminale,I))));
      end loop;

 
 
j'ai entendu parler de pondération, mais je vois pas comment pondérer correctement cette somme.
j'ai bien un exemple, mais il est adapté a un Jeu de Taquin faisant toujours 3x3
 
Bonne journé à tous , sauf à Giz   , dont j'attend avec impatience le retour sur le topic
Bonne continuation
 

 
Bonjour,
 
Et bien je suis toujours sur le sujet, un taquin N*M avec un vide en K*L, et c'est pas gagné
 
Pour reprendre les 4 points de mon message précédent a propos de l'algorithme A star , je dirais que
 
1 : je sais un peut mieu ce que je doit faire de pere(s) = n, bien que, il me manque un ou deux element au final,    
 
2 : j'ai trouvé une distance plus complexe que celle que j'ai trouvé tous seul (la distance de manhatan en fait) mais qui marche pas,
    =>  

 
   mais alors la, pour evaluer les successeurs en tournant dans le sens des aiguilles d'une montre, ça va etre un peut chaud, et puis ça me parait un peut trop simple encore.  
 
3 : j'ai, trouver l'élement min, qui est en fait toujour le premier element d'une structure maintenue trié selon les deux critères h(n) et f(n)
 
4 : l'algorithme tourne un peut, c'est à dire qu'il lui arrive de trouver une solution (optimale). mais il faut pas que le taquin soit trop melangé
      la liste des permutations obtenue dans l'ensemble fermé est maintenant continue,
      c'est à dire que je permute des elements contiguës dans la matrice
      Normal me dirais-vous vue les trois premiers points
 
Voila le topo,  
 
En priorité, je suis à la recherche d'un calcul de distance pour le jeu du Taquin.
IL doit bien y en avoir de valable, vue qu'on joue aux echec, je vois pas pourquoi on  jouerait pas au Jeu du Taquin
les echec, c'est quant même plus complex à priori  
 
Bonne journé, bonne semaine, bonne continuation

Pour le calcul de la distance de manhattan d'un plateau, c'est pas très dur quand même
 
indice : avec les opérateurs +, / et % tu devrais t'en sortir.

Malgres mes preocupations au sujet du calcul de distance,
je m'inquiète également pour cette procedure Add    
 
Il s'agit de la procedure Add de la "Structure" Open de l'algorithme A star, de laquelel je dois extraire l'élément min
 
Cette procedure Add est sensé maintenir une liste simplement chaînée trié selon deux critères
 
Dans l'ordre croissant selon ucost, et decroissant selon hcost, a moins que ce soit l'inverse, je suis telement perdu, enfin je crois que c'est ça
 
 
Mon principale souci ce porte sur les operateurs de comparaison,
En effet, oû faut-il eventuellement placer des operateurs strictes
 
j'ai bien fait des tests, mais comme dans tout les cas, le resultat n'est pas probant, je n'ai pas d'élément de comparaison
 
L'implémentation ci-desous est écrite avec le langage Ada,
 
Le code dans sont etat ::=

procedure Add(Ensemble : in out T_Ensemble ;
                   Ptr : T_Ptr_Place_Ensemble)   is
 
        Courant : T_Ptr_Place_Ensemble := Ensemble.Tete;
        Precedent : T_Ptr_Place_Ensemble := null;
 
     begin
        if Ensemble.Tete = null then
           Ensemble.Tete := Ptr;
           Ensemble.Longueur := Ensemble.Longueur + 1;
        elsif Ensemble.Longueur < 2 then
           if Ptr.ucost < Courant.ucost and
             Ptr.hcost >= Courant.hcost then
              Precedent := Ensemble.Tete;
              Ensemble.Tete := Ptr;
              Ensemble.Tete.Suivant := Precedent;
              Ensemble.Longueur := Ensemble.Longueur + 1;
           else
              Ensemble.Tete.Suivant := Ptr;
              Ensemble.Longueur := Ensemble.Longueur + 1;
           end if;
        else
           while Courant.Suivant /= null and then
             Ptr.ucost > Courant.ucost loop
              Precedent := Courant;
              Courant := Courant.Suivant;
           end loop;
           while Courant.Suivant /= null and then
             Ptr.hcost < Courant.hcost loop
              Precedent := courant;
              Courant := Courant.Suivant;
           end loop;
           if Precedent = null then
              Precedent := Ensemble.Tete;
              Ensemble.Tete := Ptr;
              Ensemble.Tete.Suivant := Precedent;
           else
              Precedent.Suivant := Ptr;
              Ptr.Suivant := Courant;
           end if;
           Ensemble.Longueur := Ensemble.Longueur + 1;
        end if;
     end Add;

 
Merci à ceux qui planchent  

 
Alors la, je suis sur les fesses parce que Manhattan je croyais qu'un '+' ou un '-' suffisais
 
Manhattan = nombre de tuiles en place    NON ?  

 
Bon j'ai dis n'importe quoi ! mais c'est ça non ?
 

for I in 0..N*M-1 loop
 
              Somme := Somme + ((abs(Absisse(Courante,I) - Absisse(terminale,I)) +
 
                                abs(ordonnee(Courante,I) - ordonnee(terminale,I))));
 
           end loop;

 
On la trouve aussi sous la forme hypoténuse, c'est pareil Non    
 

Pour mon probleme d'operateur stricte ou non, ben je sais pas trop si c'est l'essentiel du probleme
 
En effet, je resouds maintenant une matrice 3x3 dans un temps admissible et une solution optimale à la clef
 
mais pour une matrice 4x4 par exemple, c'est désastreu,
 
a mon avis mon implémentation de l'algorithme A star est correcte,
mais c'est le calcul de distance, je me repete, qu'il faut adapter à la resolution d'une matrice 4x4, voir quelconque
 
Mais Giz est de retour, alors Giz, que fais-tul avec un % dans le calcul de la distance de Manhatan ?

Je resoud rien que des cas particuliés oû la matrice n'est pas trop mélangée.
Rien de rien, même pas une matrice 3x3 en fait
zut alors, j'y ais cru  

 
Je donne ma langue au chat    
 
Pour trois raison, 1 : %   , 2 % et Manhattan   , 3 j'ai beau reflechire a une methode de calcul des chemins (depuis deux ou trois jours), je trouve rien, mais je desespere pas, Comme je l'ai déjà dis, on joue bien aux echec, alors pourquoi pas au jeu du Taquin