Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
8459 connectés 

 


 Mot :   Pseudo :  
 
 Page :   1  2  3  4  5  6  7  8  9  10  11  12  13  14  15
Auteur Sujet :

[Ada][Topic Unic][Open Source] Je fais péter mes codes.

n°2546335
Profil sup​primé
Posté le 25-05-2006 à 11:05:05  answer
 

Reprise du message précédent :
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

Code :
  1. for I in mouvement loop


il faut alors rejouter ce test

Code :
  1. if (Mouvement(I) (Absisse(Noeud_Courant.Matrice ,0),       -- si mouvement(i) /= 0
  2.                       Ordonnee(Noeud_Courant.Matrice ,0),
  3.                       Noeud_Courant.Matrice) /= 0) then


 
générer la nouvelle matrice

Code :
  1. Nouveau_Successeur := Noeud_Courant.Matrice;
  2.           Permuter(Nouveau_Successeur,
  3.                Mouvement(I)
  4.                (Absisse(Nouveau_Successeur ,0),       -- si mouvement(i) /= 0
  5.                 Ordonnee(Nouveau_Successeur ,0),
  6.                 Nouveau_Successeur);


 
ce qui donne pour le moment
 

Code :
  1. -----------------------------------------------------------------------
  2.   --               Resolution du Jeu du Taquin                         --
  3.   -----------------------------------------------------------------------
  4.   procedure Astar (Dans : in out T_Jeu_Du_Taquin) is
  5.   -----------------------------------------------------------------------
  6.   --                      Algorithme A* ou Astar                       --
  7.   -----------------------------------------------------------------------
  8.      Succes : Boolean := Boolean'Value("FALSE" );
  9.      Noeud_Courant : T_Place_Ensemble;
  10.      Nouveau_Successeur : T_Matrice;
  11.   begin
  12.      ajouter(Ensemble => Dans.Ouvert,Avec => Dans.Matrice_melangee);
  13.      Vider(Ensemble => Dans.Ferme);
  14.      while not Est_Vide(Dans.Ouvert) and not Succes loop
  15.         Noeud_courantt := L_Element_Min(Ensemble => Dans.Ouvert).all;
  16.         if -- la j'ai pas le test je comprend plus -- then
  17.           Succes := Boolean'Value("TRUE" );
  18.         else
  19.            Supprimer_noeud(Ensemble => Dans.Ouvert,Avec => Noeud_courant.id);
  20.            ajouter(Ensemble => Dans.Fermer,Nouveau => Noeud_Courant.matrice);
  21.            for I in Mouvement'range loop
  22.               if (Mouvement(I)
  23.                  (Absisse(Noeud_Courant.Matrice ,0),       -- si mouvement(i) /= 0
  24.                   Ordonnee(Noeud_Courant.Matrice ,0),
  25.                   Noeud_Courant.Matrice) /= 0) then
  26.  
  27.                  -- generer la nouvelle matrice
  28.                  Nouveau_Successeur := Noeud_Courant.Matrice;
  29.                  Permuter(Nouveau_Successeur,
  30.                           Mouvement(I)
  31.                           (Absisse(Nouveau_Successeur ,0),       -- si mouvement(i) /= 0
  32.                            Ordonnee(Nouveau_Successeur ,0),
  33.                            Nouveau_Successeur);
  34.  
  35.  
  36.  
  37.  
  38.                  -- la je pense que l'algo doit varier en fonction de sont utilisation
  39.  
  40.                  if not Esiste(Ensemble => Dans.Ouvert,L_Element => Nouveau_Successeur) and
  41.                    not Esiste(Ensemble => Dans.fermer,L_Element => Nouveau_Successeur) then
  42.                     -- la y a un chmilblic -- on vient de supprimer Noeud_courant de Ouvert est on doit lui ajouter un fils, c'es
  43. t louche
  44.                     Ajouter(Ensemble => Dans.ferme, Avec =>  Nouveau_Successeur);
  45.                     g(s) := g(n) + coût(n,s);  -- la je sais pas quoi faire de cette ligne
  46.                  elsif (g(s) > g(n) + coût(n,s)) then -- la pareil
  47.                     Ajouter(Ensemble => Dans.Fermer, Avec => Nouveau_Successeur);
  48.                     g(s) = g(n) + coût(n,s);
  49.                     if Existe(Ensemble => Dans.Ferme, L_Element => Nouveau_success)s se trouve dans fermés) then
  50.                        -- la, je comprend plus non plus, on vient de rajouter Nouveau_successeur a ferme et on test s'il y est ?
  51.                        -- le reste, c'est pire donc
  52.                        fermés  = fermés  - S;
  53.                        ouverts = ouverts + S;
  54.                        --
  55.                        -- je doit me planter quelque part !!!!!
  56.                     end if;
  57.                  end if;
  58.               end if;
  59.            end loop;
  60.  
  61.         end if;
  62.  
  63.      end loop;
  64.  
  65.   -----------------------------------------------------------------------
  66.   --                     Fin algorithme A* ou Astar                    --
  67.   -----------------------------------------------------------------------
  68.  
  69.   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

Code :
  1. -----------------------------------------------------------------------
  2.   --               Resolution du Jeu du Taquin                         --
  3.   -----------------------------------------------------------------------
  4.   procedure Astar (Dans : in out T_Jeu_Du_Taquin) is
  5.   -----------------------------------------------------------------------
  6.   --                      Algorithme A* ou Astar                       --
  7.   -----------------------------------------------------------------------
  8.      Succes : Boolean := Boolean'Value("FALSE" );
  9.      Noeud_Courant : T_Place_Ensemble;
  10.      Nouveau_Successeur : T_Matrice;
  11.   begin
  12.      ajouter(Ensemble => Dans.Ouvert,Avec => Dans.Matrice_melangee);
  13.      Vider(Ensemble => Dans.Ferme);
  14.      while not Est_Vide(Dans.Ouvert) and not Succes loop
  15.         for I in Mouvement'range loop
  16.            if (Mouvement(I)
  17.                (Absisse(Noeud_Courant.Matrice ,0),       -- si mouvement(i) /= 0
  18.                 Ordonnee(Noeud_Courant.Matrice ,0),
  19.                 Noeud_Courant.Matrice) /= 0) then
  20.  
  21.               Noeud_courant := L_Element_Min(Ensemble => Dans.Ouvert).all;
  22.               if -- la j'ai pas le test je comprend plus -- then
  23.                 Succes := Boolean'Value("TRUE" );
  24.               else
  25.                  Supprimer_noeud(Ensemble => Dans.Ouvert,Avec => Noeud_courant.id);
  26.                  ajouter(Ensemble => Dans.Fermer,Nouveau => Noeud_Courant.matrice);
  27.  
  28.                  -- generer la nouvelle matrice
  29.                  Nouveau_Successeur := Noeud_Courant.Matrice;
  30.                  Permuter(Nouveau_Successeur,
  31.                           Mouvement(I)
  32.                           (Absisse(Nouveau_Successeur ,0),       -- si mouvement(i) /= 0
  33.                            Ordonnee(Nouveau_Successeur ,0),
  34.                            Nouveau_Successeur);
  35.  
  36.  
  37.  
  38.  
  39.                  -- la je pense que l'algo doit varier en fonction de sont utilisation
  40.  
  41.                  if not Esiste(Ensemble => Dans.Ouvert,L_Element => Nouveau_Successeur) and
  42.                    not Esiste(Ensemble => Dans.fermer,L_Element => Nouveau_Successeur) then
  43.                     -- la y a un chmilblic -- on vient de supprimer Noeud_courant de Ouvert est on doit lui ajouter un fils, c'es
  44. t louche
  45.                     Ajouter(Ensemble => Dans.ferme, Avec =>  Nouveau_Successeur);
  46.                     g(s) := g(n) + coût(n,s);  -- la je sais pas quoi faire de cette ligne
  47.                  elsif (g(s) > g(n) + coût(n,s)) then -- la pareil
  48.                     Ajouter(Ensemble => Dans.Fermer, Avec => Nouveau_Successeur);
  49.                     g(s) = g(n) + coût(n,s);
  50.                     if Existe(Ensemble => Dans.Ferme, L_Element => Nouveau_success)s se trouve dans fermés) then
  51.                        -- la, je comprend plus non plus, on vient de rajouter Nouveau_successeur a ferme et on test s'il y est ?
  52.                        -- le reste, c'est pire donc
  53.                        fermés  = fermés  - S;
  54.                        ouverts = ouverts + S;
  55.                        --
  56.                        -- je doit me planter quelque part !!!!!
  57.                     end if;
  58.                  end if;
  59.               end if
  60.            end if;;
  61.         end loop;
  62.      end loop;
  63.  
  64.   -----------------------------------------------------------------------
  65.   --                     Fin algorithme A* ou Astar                    --
  66.   -----------------------------------------------------------------------


 
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 !  ;)

mood
Publicité
Posté le 25-05-2006 à 11:05:05  profilanswer
 

n°2546336
Profil sup​primé
Posté le 25-05-2006 à 12:39:24  answer
 

[:trotter88]  
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,  :heink:  
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.  [:kernel-panic]  
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
 

n°2546337
Profil sup​primé
Posté le 25-05-2006 à 13:57:13  answer
 

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  :??:  

Code :
  1. Function Distance_A_L_initiale(Courante : T_Matrice ; initiale : T_Matrice) return natural is
  2.         Somme : Natural := 0;
  3.  
  4.      begin
  5.         for I in 0..N*M-1 loop
  6.            Somme := Somme + (abs(Absisse(Courante,I) - Absisse(Source,I)) +
  7.                              abs(ordonnee(Courante,I) - ordonnee(Source,I)));
  8.         end loop;
  9.         Retrun Somme;
  10.      end Distance_A_L_initiale;


Code :
  1. Function Distance_A_La_terminale(Courante : T_Matrice ; terminale : T_Matrice) return natural is
  2.         Somme : Natural := 0;
  3.  
  4.      begin
  5.         for I in 0..N*M-1 loop
  6.            Somme := Somme + (abs(Absisse(Courante,I) - Absisse(terminale,I)) +
  7.                              abs(ordonnee(Courante,I) - ordonnee(terminale,I)));
  8.         end loop;
  9.         Retrun Somme;
  10.      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  
 

n°2546338
Profil sup​primé
Posté le 25-05-2006 à 15:38:53  answer
 

j'ai oublié une adition dans Distance_A_La_Terminale

Code :
  1. Function Distance_A_La_terminale(Courante : T_Matrice ; Initiale,Terminale : T_Matrice) return natural is
  2.      Somme : Natural := 0;
  3.  
  4.   begin
  5.      for I in 0..N*M-1 loop
  6.         Somme := Somme + (abs(Absisse(Courante,I) - Absisse(terminale,I)) +
  7.                           abs(ordonnee(Courante,I) - ordonnee(terminale,I)));
  8.         Somme := Somme + Distance_A_L_Initiale(Courante,Initiale);
  9.      end loop;
  10.      Return Somme;
  11.   end Distance_A_La_terminale;

n°2546339
Profil sup​primé
Posté le 25-05-2006 à 16:08:04  answer
 

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  :heink:  
 

Code :
  1. procedure Astar (Dans : in out T_Jeu_Du_Taquin) is
  2.   -----------------------------------------------------------------------
  3.   --                      Algorithme A* ou Astar                       --
  4.   -----------------------------------------------------------------------
  5.      Succes : Boolean := Boolean'Value("FALSE" );
  6.      Noeud_Courant : T_Place_Ensemble;
  7.      Nouveau_Successeur : T_Matrice;
  8.   ------------------------------------------------------------------------
  9.   --   la fonction qui retourn l'element avec la distance minimale      --
  10.   function L_Element_Min (Ensemble : T_Ensemble) Return T_Place_Ensemble is
  11.      Courant : T_Ptr_Place_ensemble := Ensemble.Tete;
  12.      Element_Min : T_Ptr_Place_Ensemble := Ensemble.Tete;
  13.   begin
  14.      while Ensemble.Courant /= null loop
  15.         if Distance_A_La_Terminale(Ensemble.Courant.Matrice,Dans.Matrice_Melangee,Dans.Matrice_Initiale) +
  16.           Distance_A_L_initiale(Ensemble.Courant.Matrice,Dans.Matrice_melangee) <
  17.           Distance_A_La_Terminale(Element_Min.Matrice,Dans.Matrice_Melangee,Dans.Matrice_Initiale) +
  18.           Distance_A_L_initiale(Element_Min.Matrice,Dans.Matrice_melangee) then
  19.            Element_Min := Ensemble.Courant;
  20.         end if;
  21.         Courant := Courant.Suivant;
  22.      end loop;
  23.      return Element_Min.all;
  24.   end L_Element_Min;
  25.  
  26.  
  27.  
  28.   task Gadget_Affichage is
  29.      entry Maj (compteur : Positive;Matrice : T_matrice);
  30.   end;
  31.   task body Gadget_Affichage is
  32.      Local_Compteur : Positive;
  33.   begin
  34.  
  35.      loop
  36.  
  37.         accept Maj(Compteur : Positive;Matrice : T_matrice) do
  38.            Local_Compteur := Compteur;
  39.            Clear_return := System("clear" & Ascii.Nul);
  40.            Afficher(Matrice);
  41.            Put("Compteur de matrices : " & Integer'Image(Local_Compteur));
  42.         end Maj;
  43.      end loop;
  44.   end Gadget_Affichage;
  45.  
  46.   Count : Natural := 0; -- Nombre de matrices generees
  47.   begin
  48.      Put_Line("DEBUT" );
  49.      ajouter(Ensemble => Dans.Ouvert,Avec => Dans.Matrice_melangee);
  50.      Vider(Ensemble => Dans.Ferme);
  51.      while not Est_Vide(Dans.Ouvert) and not Succes loop
  52.         Put_Line("TOTO-0" );
  53.         for I in solution'range loop
  54.            Put_Line("TOTO-0-1" );
  55.            Noeud_courant := L_Element_Min(Ensemble => Dans.Ouvert);
  56.            if (solution(I)
  57.                (Absisse(Noeud_Courant.Matrice ,0),       -- si mouvement(i) /= 0
  58.                 Ordonnee(Noeud_Courant.Matrice ,0),
  59.                 Noeud_Courant.Matrice) /= 0) then
  60.               Put_Line("TOTO-1" );
  61.  
  62.               if Sont_Egales(Gauche => Noeud_Courant.Matrice, Droit => Dans.Matrice_Initiale) then
  63.                 Succes := Boolean'Value("TRUE" );
  64.               else
  65.                  Put_Line("TOTO-2" );
  66.                  Supprimer_noeud(Ensemble => Dans.Ouvert,element => Noeud_courant.matrice);
  67.                  Put_Line("TOTO-2-1" );
  68.                  ajouter(Ensemble => Dans.Ferme, avec => Noeud_Courant.matrice);
  69.                  Put_Line("TOTO-2-2" );
  70.                  -- generer la nouvelle matrice
  71.                  Nouveau_Successeur := Noeud_Courant.Matrice;
  72.                  Put_Line("TOTO-2-3" );
  73.                  Permuter(Nouveau_Successeur,
  74.                           solution(I)
  75.                           (Absisse(Nouveau_Successeur ,0),       -- si mouvement(i) /= 0
  76.                            Ordonnee(Nouveau_Successeur ,0),
  77.                            Nouveau_Successeur));
  78.                  -- la je pense que l'algo doit varier en fonction de sont utilisation
  79.                  Put_Line("TOTO-2-4" );
  80.                  if not Existe(Ensemble => Dans.Ouvert,L_Element => Nouveau_Successeur) and
  81.                    not Existe(Ensemble => Dans.ferme,L_Element => Nouveau_Successeur) then
  82.                     Put_Line("TOTO-3-1" );
  83.                     -- la y a un chmilblic -- on vient de supprimer Noeud_courant de Ouvert est on doit lui ajouter un fils, c'est l
  84. ouche
  85.                     Ajouter(Ensemble => Dans.ferme, Avec =>  Nouveau_Successeur);
  86.                  elsif Distance_A_L_initiale(Nouveau_Successeur,Dans.Matrice_Melangee) > Distance_A_L_initiale(Nouveau_Successeur,Da
  87. ns.Matrice_Melangee) + Distance_A_La_terminale(Nouveau_Successeur,Dans.Matrice_Melangee,Dans.Matrice_initiale) then
  88.                     Put_Line("TOTO-3-2" );
  89.                     Ajouter(Ensemble => Dans.Ferme, avec => Nouveau_Successeur);
  90.                     if Existe(Ensemble => Dans.Ferme, L_Element => Nouveau_successeur) then
  91.                        Put_Line("TOTO-4" );
  92.                        -- la, je comprend plus non plus, on vient de rajouter Nouveau_successeur a ferme et on test s'il y est ?
  93.                        -- le reste, c'est pire donc
  94.                        Supprimer_noeud(Ensemble => Dans.Ferme, Element => Nouveau_Successeur);
  95.                        Ajouter(Ensemble => Dans.Ouvert, Avec => Nouveau_Successeur);
  96.                        --
  97.                        -- je doit me planter quelque part !!!!!
  98.                     end if;
  99.                  end if;
  100.               end if;
  101.               Count := Count + 1;
  102.               Gadget_Affichage.Maj(Count,Nouveau_successeur);
  103.            end if;
  104.         end loop;
  105.      end loop;
  106.   -----------------------------------------------------------------------
  107.   --                     Fin algorithme A* ou Astar                    --
  108.   -----------------------------------------------------------------------
  109.   end Astar;


 
Gadget_Affichage c'est pour afficher des infos pendant le resolution

n°2546340
Profil sup​primé
Posté le 25-05-2006 à 16:26:36  answer
 

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

n°2546341
Profil sup​primé
Posté le 25-05-2006 à 19:36:42  answer
 

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


Message édité par Profil supprimé le 25-05-2006 à 19:40:43
n°2546342
Profil sup​primé
Posté le 25-05-2006 à 19:57:57  answer
 

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 :pt1cable:  
 
 

Code :
  1. ------------------------------------------------------------------------
  2.   --   la fonction qui retourn l'element avec la distance minimale      --
  3.   --   Methode : parcourt total de la liste
  4.  
  5.   function L_Element_Min (Ensemble : T_Ensemble) Return T_Place_Ensemble is
  6.      Courant : T_Ptr_Place_ensemble := Ensemble.Tete;
  7.      Element_Min : T_Ptr_Place_Ensemble := Ensemble.Tete;
  8.   begin
  9.      Put_Line("TOTO-11" );
  10.      if Courant = null then
  11.         raise Program_Error;
  12.      end if;
  13.      while Courant.suivant /= null loop
  14.         Put_Line("TOTO-11-1" );
  15.         if (Distance_A_La_Terminale(Courant.Matrice,Dans.Matrice_melangee,Dans.Matrice_Initiale) +
  16.           Distance_A_L_initiale(Courant.Matrice,Dans.Matrice_melangee)) <
  17.           (Distance_A_La_Terminale(Element_Min.Matrice,Dans.Matrice_Melangee,Dans.Matrice_Initiale) +
  18.           Distance_A_L_initiale(Element_Min.Matrice,Dans.Matrice_melangee)) then
  19.            Put_Line("TOTO-12" );
  20.            Element_Min := Courant;
  21.         end if;
  22.         Put_Line("TOTO-13" );
  23.         Courant := Courant.Suivant;
  24.      end loop;
  25.      Put_Line("TOTO-14" );
  26.      return Element_Min.all;
  27.   end L_Element_Min;


Merci pour votre aide

n°2546343
Profil sup​primé
Posté le 25-05-2006 à 23:43:09  answer
 

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

n°2546344
Profil sup​primé
Posté le 26-05-2006 à 10:53:54  answer
 

je me suis encore trompé de topic, c'est ici qu'il faut que je poste ça
 
:hello:  
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

Code :
  1. for I in 0..N*M-1 loop
  2.         Somme := Somme + ((abs(Absisse(Courante,I) - Absisse(terminale,I)) +
  3.                           abs(ordonnee(Courante,I) - ordonnee(terminale,I))));
  4.      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
 

mood
Publicité
Posté le 26-05-2006 à 10:53:54  profilanswer
 

n°2546345
Profil sup​primé
Posté le 29-05-2006 à 10:01:27  answer
 

:hello:  
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,
    =>  


h(n)=distance_de_manatthan(n)+3*score de déplacement(n).
 
score de déplacement de n= somme des scores des cases du taquin:
 
    * - le pavé central a une valeur de 1
    * - un pavé non central vaut 0 si son successeur se trouve juste après lui en tournant dans le sens des aiguilles d'une montre
    * - tous les autres valent 2  
 
 
   (quant ils parlent du pavé central, c'est parce que dans leur cas le vide est placé au centre)  

 
   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

n°2546346
Giz
Posté le 29-05-2006 à 12:30:23  profilanswer
 

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

n°2546347
Profil sup​primé
Posté le 29-05-2006 à 12:45:57  answer
 

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 ::=

Code :
  1. procedure Add(Ensemble : in out T_Ensemble ;
  2.                   Ptr : T_Ptr_Place_Ensemble)   is
  3.  
  4.        Courant : T_Ptr_Place_Ensemble := Ensemble.Tete;
  5.        Precedent : T_Ptr_Place_Ensemble := null;
  6.  
  7.     begin
  8.        if Ensemble.Tete = null then
  9.           Ensemble.Tete := Ptr;
  10.           Ensemble.Longueur := Ensemble.Longueur + 1;
  11.        elsif Ensemble.Longueur < 2 then
  12.           if Ptr.ucost < Courant.ucost and
  13.             Ptr.hcost >= Courant.hcost then
  14.              Precedent := Ensemble.Tete;
  15.              Ensemble.Tete := Ptr;
  16.              Ensemble.Tete.Suivant := Precedent;
  17.              Ensemble.Longueur := Ensemble.Longueur + 1;
  18.           else
  19.              Ensemble.Tete.Suivant := Ptr;
  20.              Ensemble.Longueur := Ensemble.Longueur + 1;
  21.           end if;
  22.        else
  23.           while Courant.Suivant /= null and then
  24.             Ptr.ucost > Courant.ucost loop
  25.              Precedent := Courant;
  26.              Courant := Courant.Suivant;
  27.           end loop;
  28.           while Courant.Suivant /= null and then
  29.             Ptr.hcost < Courant.hcost loop
  30.              Precedent := courant;
  31.              Courant := Courant.Suivant;
  32.           end loop;
  33.           if Precedent = null then
  34.              Precedent := Ensemble.Tete;
  35.              Ensemble.Tete := Ptr;
  36.              Ensemble.Tete.Suivant := Precedent;
  37.           else
  38.              Precedent.Suivant := Ptr;
  39.              Ptr.Suivant := Courant;
  40.           end if;
  41.           Ensemble.Longueur := Ensemble.Longueur + 1;
  42.        end if;
  43.     end Add;


 
Merci à ceux qui planchent  :p

n°2546348
Profil sup​primé
Posté le 29-05-2006 à 12:48:57  answer
 

Giz a écrit :

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


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

n°2546349
Profil sup​primé
Posté le 29-05-2006 à 12:59:51  answer
 


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

Code :
  1. for I in 0..N*M-1 loop
  2.  
  3.              Somme := Somme + ((abs(Absisse(Courante,I) - Absisse(terminale,I)) +
  4.  
  5.                                abs(ordonnee(Courante,I) - ordonnee(terminale,I))));
  6.  
  7.           end loop;


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

n°2546350
Profil sup​primé
Posté le 29-05-2006 à 13:39:55  answer
 

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 ?

n°2546351
Profil sup​primé
Posté le 29-05-2006 à 14:51:44  answer
 

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  :cry:

n°2546352
Profil sup​primé
Posté le 29-05-2006 à 15:46:14  answer
 

Giz a écrit :

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


 
Je donne ma langue au chat  :p  
 
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  :??:

n°2546353
Giz
Posté le 29-05-2006 à 16:46:08  profilanswer
 

indice 2 : utilise un tableau pour représenter le plateau. Ex : [1, 3, 5, 7, 8, 2, 4, 6, X]. En partant de la valeur du tableau dans une case et de l'indice correspondant à cette case tu arrives à déterminer Où la valeur (le jeton) est et où il doit être => et donc tu peux calculer la distance de manhattan à partir de là (le signe - peut être nécessaire en fait).

n°2546354
Profil sup​primé
Posté le 29-05-2006 à 18:01:29  answer
 

Pardonne moi d'avance, Giz, je suis peut-etre dans l'erreur, mais je calcule déjàs la distance de Manhattan
en faisant la somme des sommes des differences entre les absisses des matrices courante et terminale et
 des differences entre les ordonnees des matrices courante et terminale,
 
Enfin bref ça doit revenir au même, mais ça marche pas, alors je vais faire un tableau 1d pour voir
 ....
 .....
 .....
Un peut plus tard à Nîmes,
 
Et bien ça ne marche pas mieu avec une comparaison dans un tableau 1d, c'était à prévoir
Y a un hic quelque part  [:kernel-panic]  
 
 
Comme je suis assé sur de moi sur le coup de la distance de Manhattan
je me demande si j'ai bien implémenté l'algo A star,
si oui alors je pourais en deduire avec certitude que la distance de Manhattan est insuffisante à la resolution
d'un Taquin même 3x3,
 
Quand je pense que tu resouds, Giz,  un Taquin 4x4 en moins de 10 secondes .... Mais comment fais-tu ?
 
je met les sources Ada de Taquin 14 à disposition ICI
l'algo A star est implémenté dans p_taquin.adb

n°2546355
Giz
Posté le 30-05-2006 à 09:49:51  profilanswer
 

Avant de coder l'algo A*, il serait bien d'apprendre à savoir coder le problème  :ange: . Coder un problème ne dépend pas de A*. Coder le problème (savoir établir ses successeurs et evaluer un plateau) est indépendant de la méthode de résolution, hein  :sarcastic: .
 
Indice 3 : une heuristique admissible plus facile à coder alors est compter le nombre de pièces mal placées. (entre 0 et 9 pour u taquin 3*3). Et ca dis moi pas que tu n'y arrives pas...

n°2546356
Profil sup​primé
Posté le 30-05-2006 à 10:22:01  answer
 

Giz a écrit :

Avant de coder l'algo A*, il serait bien d'apprendre à savoir coder le problème  :ange: . Coder un problème ne dépend pas de A*. Coder le problème (savoir établir ses successeurs et evaluer un plateau) est indépendant de la méthode de résolution, hein  :sarcastic: .
 
Indice 3 : une heuristique admissible plus facile à coder alors est compter le nombre de pièces mal placées. (entre 0 et 9 pour u taquin 3*3). Et ca dis moi pas que tu n'y arrives pas...


 
Bonjour Giz,
Pourquoi dis-tu que je n'y arrive pas, je calcul la distance de Manhattan, je compte les pièces mal placées sans problème à priori
quant au successeur je les connais tres bien, je melange judicieusement mon Taquin avec
 
Mais Manhattan ne suffis pas, j'en ai la preuve !!
 
0|7|X
8|X|X
X|X|X
 
le zero est l'element vide et est à ça place,
7 et 8 sont ces unique successeur, et leur permutation augmente la listance de Manhattan
Alors, effectivement il faut tirer sur la corde ce se placer deans une situation pareil, je ne sai pas si elle est valide, apriori oui
 
pour mon calcul de distance, j'en suis, simplement a cumuler la distance de Manhattan et le nombre de piece mal placées
mais soit ça suffit pas, soit j'ai une erreur dans A star


Message édité par Profil supprimé le 30-05-2006 à 10:22:56
n°2546357
Profil sup​primé
Posté le 30-05-2006 à 12:50:41  answer
 

Et voila, pour les matrices 3x3 en tout cas, cette fois je croix que je tien le bon bout
 
Au lieu de trier les elements selon leur distance au but d'abord puis selon leur distance a l'initiale en suite,
comme il est prescrit dans certaine publication, je trie les elements selon la somme des distances
 
Giz, dis moi si je me trompe  :p  
 
donc a par les cas particulier comme celui dont je parle dans mon message precedent, ça marche
pour les matrices 3x3. Temps de resolution ~= 45 secondes (sur un pc mono proc 2.6 GHertz), nombre de matrice générée ~= 1400, nombre de permutation pour arriver au but 19, alors que le nombre de mouvement efefctué pour le melange est ~= 200
 
Voila pas mieu pour le moment, j'attend les resultat sur une matrice 4x4,

n°2546358
Giz
Posté le 30-05-2006 à 13:31:43  profilanswer
 

ben voilà, t'a fini par y arriver alors. Donne moi ton plateau de départ et ton plateau d'arrivé, que j'observe mes résultats avec :).

n°2546359
Profil sup​primé
Posté le 30-05-2006 à 15:44:34  answer
 

un plateau de depart,  
 
3|2|6
8|7|4
0|5|1
 
 
plateau d'arriver
 
1|4|7
2[5|8
3|6|0
 
 
23 coup pour le ranger

n°2546360
Giz
Posté le 30-05-2006 à 16:38:51  profilanswer
 

et les résultats du benchmark stp...

n°2546361
Profil sup​primé
Posté le 30-05-2006 à 16:39:38  answer
 

j'ai une matrice  4x4 aussi ...   :sol: [:666rip666]  :sol:  
 
Plateu de depart
 
13| 9| 8| 1
 6|14| 2| 7
 5|11|0 |15
 4|10|12|3  
 
PLateau d'arrivé
 1| 5| 9|12
 2| 6|10|13
 3| 7| 0|14
 4| 8|11|15
 
en 61 coups
 
 
je lance 5x5 maintenant, pour voir mais je crois que j'ai trouvé la difference entre les matrices de différentes taille,
 

n°2546362
Giz
Posté le 30-05-2006 à 16:49:45  profilanswer
 


 
 :ouch: , je n'ai jamais réussi à trouver des solutions s'y profonde !! (combien de temps mets-tu et combien de mémoire ça te prends ?)
...si 61 coups est bien l'optimal, chapeau mec !  :ouch:  
Si ça marche avec 5*5, alors là, tu fais mieux que moi !  [:wam]

n°2546363
Profil sup​primé
Posté le 30-05-2006 à 16:55:32  answer
 

Giz a écrit :

et les résultats du benchmark stp...


 
je te donne un autre plateau pour lequel j'ai le nombre de plateau généré mais je peut faire varier ce nombre,
je n'ai pas encore trouvé l'optimal Manhattan*((N*M)/2) ou Manhatan*(((N*M)/2)-1) ou un autre , je sais pas encore
 
Nombre de Plateau généré avec heuristic = Manhattan*((N*M)/2) + count_mal_placés == 1800
 
Plateau de depart
 
7|5|3
1|6|2
8|4|0
 
Pateau d'arrivé
 
1|4|7
2|5|8
3|6|0
 
Nombre de deplacement 27

n°2546364
Profil sup​primé
Posté le 30-05-2006 à 17:04:25  answer
 

POur la memoire, je sais pas, pas baucoup à mon avis pour un ematrice 3x3 ou 4x4 même, apres sa doit etre proportionnel
pour les temps, pour une matrice 3x3 ou 4x4 c'est le l'ordre de 30 à 50 secondes
 
je lance 5x5

n°2546365
Profil sup​primé
Posté le 30-05-2006 à 17:07:00  answer
 

ououps ..  [:dawa_neowen]  
 
j'ai dis une bétise avec Manhattan*((N+M)/2) ou Manhatan*(((N+M)/2)-1)
 
ça devrais suffire

n°2546366
Giz
Posté le 30-05-2006 à 17:16:21  profilanswer
 


 
 :ange:  :ange: ... en sommant les 2 heuristiques, tu n'obtiens pas une valeur heuristique admissible  :o => ta solution n'est pas optimale !

n°2546367
Profil sup​primé
Posté le 30-05-2006 à 17:31:47  answer
 

Giz a écrit :

:ange:  :ange: ... en sommant les 2 heuristiques, tu n'obtiens pas une valeur heuristique admissible  :o => ta solution n'est pas optimale !


 
Pas la peine de mexpliqué, je comprendrai pas
 
Mais 5x5 avec Manhattan*((N+M)/2) + (count_mal_places*((N+M)/2))-(M+N)/2 ça marche
 
Maintenant pour te dire si c'est l'optimale  :??: je sais pas
 
Est-ce que tu fais mieu ?
 

n°2546368
Giz
Posté le 30-05-2006 à 18:06:40  profilanswer
 

Je te dirai ça dépend demain, le temps que je passe chez moi...mais la matrice 4*4, je ne les résouds pas toutes.

n°2546369
Giz
Posté le 31-05-2006 à 09:21:11  profilanswer
 

Bon en fait, j'ai pas pu prendre ton plateau d'arrivé car le mien est codé en dur dans le code et j'ai pas envie de me replonger dans le code. Donc si tu prends le même plateau d'arrivé que moi (de 1 à n puis 0 en allant de gauche à droite et de haut en bas), pour ton 1er problème 3*3, je trouve aucune solution réalisable et pour ton plateau 4*4, je n'arrive pas à le résoudre avec A* (avec 1Go de ram autorisé pourtant).

n°2546370
Profil sup​primé
Posté le 31-05-2006 à 10:15:07  answer
 

Bonjour Giz,
Bain, moi aussi c'est codé en "dur", mais je vais voir ce que je peut faire !
 
Pour ce qui est des resultats, et bien je revoie ma copie,
En effet, pour les matrice 3x3, la resolution est de l'ordre de la minute,
               pour les matrice 4x4, c'est plutot de l'odre de 10, 12 minutes pour la derniere que j'ai lancé, pas tres mélangée non plus
               pour les matrice 5x5, j'ai lancé 5x5 hier soir, il y à 14 heures, je n'est toujours pas la solution
                                                    avec une ocupation memoire de 351 Mo et 2_000_000 de matrices générées
                                                    mais ça tourne
                                                    malheuresement, je crois que "uniform" ne sera pas suffisament discréminant par rapport a la complexité du mélange et de "heuristic"
                                                    je vais donc etre obligé de recommencer le test
 

n°2546371
Profil sup​primé
Posté le 31-05-2006 à 10:59:23  answer
 


 
j'ai peut-etre dis une betise encore  [:dawa_neowen]

n°2546372
Profil sup​primé
Posté le 31-05-2006 à 11:10:53  answer
 

une matrice 3x3 dont l'ordre est celui que tu m'as specifié
 
6|4|5
1|0|7
8|3|2
 
Nombre de matrices générées ~= 2_500
Temps de resolution  ~= 33 secondes
Nombre de deplacement pour ranger cette matrice = 29
 
 
une matrice 4x4 dont l'ordre est celui que tu m'as specifié
 
  6|  1|  7|  8
12|13|10|14
  4|  5|  9 |  0
11|  2|15|  3
 
Nombre de matrices générées ~= 60_000
Temps de resolution  ~= 10minutes
Nombre de deplacement pour ranger cette matrice = 80
 
Il y a un autre parametre qui rentre en compte dans la resolution,
c'est l'ordre dans lequel tu donnes les successeurs
 

n°2546373
Profil sup​primé
Posté le 31-05-2006 à 11:22:51  answer
 

:hello:  
 
et une matrice 5x5 dans la boite    :heink:  :sol:  [:666rip666]  :sol:  
 
Occupation memoire ~= 351 Mo
temps de resolution ~= 15 heures
Nombre de deplacements = 135
Nomre de matrices généré un peut plus de 2_000_000
 
c'est pas la peine que je te la donne, les lignes est colonnes sont inversé
 
Giz,
maintenant je peut me lance dans l'implementation d'une procedure de lecture de matrice dans un fichier
pour je puisse tester les matrices que tu ne parviens pas à resoudre, si tu les as conservé ?

n°2546374
Giz
Posté le 31-05-2006 à 11:55:45  profilanswer
 

ouai, vas-y affiche moi la solution des problèmes insolubles que je ne résoud pas que je rigole pour voir :D. 135 déplacements ... c'est impossible de descendre à cette profondeur tout en ayant l'optimal :pfff:

n°2546375
Profil sup​primé
Posté le 31-05-2006 à 12:03:26  answer
 

Giz a écrit :

ouai, vas-y affiche moi la solution des problèmes insolubles que je ne résoud pas que je rigole pour voir :D. 135 déplacements ... c'est impossible de descendre à cette profondeur tout en ayant l'optimal :pfff:


 
J'ai pas compris ce que tu veut ?
 
Donne moi une matrice !
 
Ce soir je lance une autre matrice 5x5 avec pour uniform, seulement Manhattan, pour voir
 
Mais donne moi une matrice, soluble, que tu ne resoud pas avec ton algo !
 
edit : je voulais dire : avec pour heuristic, seulement Manhattan, pour voir


Message édité par Profil supprimé le 31-05-2006 à 12:10:23
mood
Publicité
Posté le   profilanswer
 

 Page :   1  2  3  4  5  6  7  8  9  10  11  12  13  14  15

Aller à :
Ajouter une réponse
 

Sujets relatifs
Probleme robot google ? Ma source internet ? aidez moiInterface ADA avec C
Projet de frontend Open-Source pour émulateursOpen Office: Base de données
code source pdf ?Modifier le code source de SIP-Communicator
[JS] Pb avec un page de javascripts et module open flash chart[ADA] /!\ Combien on peux boire de biere JEUDI MIDI §§§ la defense ??
Fonction window.open (javascript) 
Plus de sujets relatifs à : [Ada][Topic Unic][Open Source] Je fais péter mes codes.


Copyright © 1997-2025 Groupe LDLC (Signaler un contenu illicite / Données personnelles)