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

  FORUM HardWare.fr
  Programmation
  Ada

  [Ada][Algo] Astar ; le résultat ne me semble pas conforme

 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

[Ada][Algo] Astar ; le résultat ne me semble pas conforme

n°2546136
lady ada
Posté le 15-11-2026 à 20:31:12  profilanswer
 

Bonjour !
 
Je cherche depuis trois jours à établir le chemin pour un jeu du taquin avec Astar.
 
Mon implémentation trouve la solution. Cependant la liste ne retourne pas le chemin attendu.
 
Le résultat fourni en fin de message correspond à une parti de l'éxecution de ce bout de programme et il ne me semble pas conforme à ce qui est écrit.
En efftet, les états intermédiare du chemin du jeu ne son pas affiché comme attendu.
 

Code :
  1. procedure Astar (open : in Element_List;
  2.                close  : in out Element_List) is
  3.     
  4.     
  5.     
  6.      Openned : Node_List;    
  7.      Closed : Node_List;
  8.     
  9.      Openned_Curs : Node_Lists.Cursor;
  10.      Close_Curs : Element_Lists.Cursor;
  11.     
  12.      Done : Boolean := False;
  13.     
  14.      Initial_Node : Node_Record;
  15.      Goal : Element;
  16.      Node : Node_Record;
  17.  
  18.  
  19.      Exhausted : boolean := false;
  20.  
  21.      begin
  22.      Goal := Element_Lists.Last_Element(close);
  23.      Close_Curs := Element_Lists.First(close);
  24.      Adjust(Initial_Node, Element_Lists.First_Element(open));    
  25.      Node_Lists.Append(Openned, Initial_Node);
  26.      Element_Lists.Delete_First(Close);          
  27.      Text_Io.Put_Line("initialized !" );
  28.     
  29.     Astar_Loop :
  30.     
  31.      while not Is_Empty(Openned) loop
  32.         
  33.         U_Sorting.Sort(Openned);
  34.         H_Sorting.Sort(Openned);
  35.         declare
  36.            Openned_Find_Curs : Node_Lists.Cursor :=
  37.          Node_Lists.First(Openned);
  38.            Best_Node : Node_Record;
  39.            F : Float := 0.0;
  40.         begin
  41.            Best_Node := Node_Lists.Element(Openned_Find_Curs);
  42.            Node_Lists.Delete_First(Openned);          
  43.           
  44.            declare
  45.           Best_Successors : El_Array := Successors(Best_Node.E);
  46.           
  47.            begin
  48.           
  49.           for Succ in Best_Successors ' range loop
  50.              declare
  51.             E : Element := Best_Successors(Succ);
  52.              begin
  53.  
  54.             
  55.             if Equal(E, Goal) then
  56.             print(E);
  57.                Adjust(Node, E);              
  58.                Node.Ucost :=  Best_Node.ucost  + (Uniform(Node.E));
  59.                  Node.Hcost := (Heuristic(Node.E) + Best_Node.Hcost) + best_node.ucost;
  60.                     F := (best_node.ucost + heuristic(Node.E)) ;
  61.                  Text_Io.Put_Line("Ucost : " & float'Image(Node.ucost));
  62.                  Text_Io.Put_Line("Hcost : " & float'Image(Node.Hcost));
  63.                     Text_Io.Put_Line("F : " & Float'Image(F));
  64.                Node_Lists.Append(Closed, Node);
  65.                Text_Io.Put_Line("Goal !" );
  66.                exit Astar_Loop;                      
  67.             else
  68.                print(E);
  69.                Adjust(Node, E);
  70.  
  71.  
  72.                Node.Ucost :=  Best_Node.ucost  + (Uniform(Node.E));
  73.                Text_Io.Put_Line("Ucost : " & float'Image(Node.ucost));
  74.  
  75.                Node.Hcost := (Heuristic(Node.E) + Best_Node.Hcost) + best_node.ucost;
  76.                Text_Io.Put_Line("Hcost : " & float'Image(Node.Hcost));
  77.               
  78.  
  79.                F := (best_node.ucost + node.hcost + heuristic(Node.E)) ;
  80.                  Text_Io.Put_Line("F : " & Float'Image(F));
  81.  
  82.                if Node.Ucost + heuristic(node.E) < F then
  83.  
  84.                    Node_Lists.Append(closed, node);
  85.  
  86.                if not Node_Lists.Is_Empty(openned) then
  87.  
  88.                  declare
  89.                     Open_Curs : Node_Lists.Cursor := Node_Lists.First(Openned);
  90.                  begin
  91.                     
  92.                     declare
  93.                        Open_Node : Node_Record := Node_Lists.Element(Open_Curs);
  94.                     begin
  95.                       
  96.                        if Equal(Open_Node.E, Node.E) then
  97.                       
  98.                       Done := True;
  99.                        end if;
  100.                       
  101.                     end;
  102.                     
  103.                     if not Done then
  104.                        for Open in 1..Node_Lists.Length(openned) - 1 loop
  105.                       Open_Curs := Node_Lists.Next(Open_Curs);
  106.                       
  107.                       declare
  108.                          Open_Node : Node_Record := Node_Lists.Element(Open_Curs);
  109.                       begin
  110.                         
  111.                          if Equal(Open_Node.E, Node.E) then
  112.                         
  113.                         Done := True;
  114.                          end if;
  115.                         
  116.                       end;
  117.                       exit when Open = Node_Lists.Length(Openned);
  118.                       
  119.                       
  120.                        end loop;
  121.                     end if;
  122.                     
  123.                     
  124.                  end;
  125.  
  126.                   end if;
  127.                   if not Done then
  128.                  Node_Lists.Append(Openned, Node);
  129.  
  130.                 
  131.                   end if;
  132.  
  133.                   Done := False;
  134.  
  135.                end if;
  136.                  end if;
  137.  
  138.              end;
  139.           end loop;
  140.           
  141.            end;
  142.         end;
  143.         
  144.         
  145.      end loop Astar_Loop;
  146.     
  147.      Openned_Finalization(close, closed);
  148.  
  149.     
  150.      end Astar;


 

Init...
 1 2 3
 4 5 6
 7 8 0
Random...
Step :  6
 1 2 3
 4 5 6
 0 7 8
Init...
Astar...
initialized !
 1 2 3
 0 5 6
 4 7 8
Ucost : -1.00000E+00
Hcost :  1.00000E+00
F :  2.00000E+00
 1 2 3
 4 5 6
 7 0 8
Ucost : -1.00000E+00
Hcost :  1.00000E+00
F :  2.00000E+00
 1 2 3
 4 0 6
 7 5 8
Ucost : -2.00000E+00
Hcost :  1.00000E+00
F :  1.00000E+00
 1 2 3
 4 5 6
 0 7 8
Ucost : -2.00000E+00
Hcost :  1.00000E+00
F :  1.00000E+00
 1 2 3
 4 5 6
 7 8 0
Ucost : -2.00000E+00
Hcost :  1.00000E+00
F :  0.00000E+00
Goal !
Count :  5
List...
Press enter...
 5
 1 2 3
 0 5 6
 4 7 8
 1 2 3
 4 5 6
 7 0 8
 1 2 3
 4 0 6
 7 5 8
 1 2 3
 4 5 6
 0 7 8
 1 2 3
 4 5 6
 7 8 0
 
Astar task halted.


 
Merci pour votre aide.


---------------
main is business suite for Ada projects. Web site : inconito.net
mood
Publicité
Posté le 15-11-2026 à 20:31:12  profilanswer
 

n°2546137
lady ada
Posté le 15-11-2026 à 20:47:19  profilanswer
 

J'ai trouvé une erreur déjà.
Le problème reste entier avec l'exemple suivant.
L'implémentation ci - dessus est inchangée.
 


Init...
 1 2 3
 4 5 6
 7 8 0
Random...
Step :  6
 1 2 0
 4 5 3
 7 8 6
Init...
Astar...
initialized !
 1 0 2
 4 5 3
 7 8 6
Ucost : -1.00000E+00
Hcost :  1.00000E+00
F :  2.00000E+00
 1 2 3
 4 5 6
 7 8 0
Ucost : -1.00000E+00
Hcost :  1.00000E+00
F :  1.00000E+00
Goal !
Count :  2
List...
Press enter...
 2
 1 0 2
 4 5 3
 7 8 6
 1 2 3
 4 5 6
 7 8 0
 
Astar task halted.
 


Message édité par lady ada le 15-11-2026 à 20:49:24

---------------
main is business suite for Ada projects. Web site : inconito.net
n°2546142
lady ada
Posté le 16-11-2026 à 10:12:23  profilanswer
 

Afin de vous fournir l'ensemble des éléments impliqués dans le déroulement de ce programme ; Je vous communique les fonctions utilisées :
 

Code :
  1. Moves : Move_Array :=
  2.     (Right'Access, Down'Access, Left'Access, Up'Access);
  3.  
  4.  
  5.   function Successors (Usr : in Taquin_8x8) return Taquin_Array is
  6.      Successors : access Taquin_Array := new Taquin_Array (1..0);
  7.      buffer : access Taquin_Array;
  8.   begin
  9.      for Move in reverse Moves'Range loop
  10.      begin
  11.         if Moves(Move)(Usr) /= Usr then
  12.            Buffer := new Taquin_Array(1..Successors'Length+1);
  13.            Buffer(1..Successors'Length) := Successors.all;          
  14.            Buffer(Buffer'Last) := Moves(Move)(Usr);
  15.            Successors := new Taquin_array ' (Buffer.all);
  16.         end if;
  17.      exception
  18.         when No_Succ =>
  19.            null;
  20.      end;
  21.      end loop;
  22.      Return Successors.all;
  23.   end Successors;


 

Code :
  1. function Up (Usr : in Taquin_8x8) return Taquin_8x8 is
  2.      Node : Taquin_8x8 := Usr;
  3.      Token : Token_Type;
  4.      Done : Boolean := False;
  5.   begin
  6.      for Line in Node.Matrix'range(1) loop
  7.      for col in Node.Matrix'range(2) loop
  8.         if Node.Matrix(Line, Col).Num = 0 then
  9.            if Line > 1 then
  10.           Token := Node.Matrix(Line-1, Col);
  11.           Node.Matrix(Line-1, Col) := Node.Matrix(Line, Col);
  12.           Node.Matrix(Line, Col) := Token;
  13.           Done := True;
  14.           Step := Step + 1;
  15.            end if;
  16.            exit;
  17.         end if;
  18.      end loop;
  19.      end loop;
  20.      if not Done then
  21.      raise No_Succ;
  22.      end if;
  23.      return Node;
  24.   end Up;


 

Code :
  1. function Down (Usr : in Taquin_8x8) return Taquin_8x8 is
  2.      Node : Taquin_8x8 := Usr;
  3.      Token : Token_Type;
  4.      Done : Boolean := False;
  5.   begin
  6.      for Line in Node.Matrix'range(1) loop
  7.      for col in Node.Matrix'range(2) loop
  8.         if Node.Matrix(Line, Col).Num = 0 then
  9.            if Line < Node.Matrix'Last(1) then
  10.           Token := Node.Matrix(Line+1, Col);
  11.           Node.Matrix(Line+1, Col) := Node.Matrix(Line, Col);
  12.           Node.Matrix(Line, Col) := Token;
  13.           Done := True;
  14.           Step := Step + 1;
  15.            end if;
  16.            exit;
  17.         end if;
  18.      end loop;
  19.      end loop;
  20.      if not Done then
  21.      raise No_Succ;
  22.      end if;
  23.      return Node;
  24.   end Down;


 

Code :
  1. function Right (Usr : in Taquin_8x8) return Taquin_8x8  is
  2.      Node : Taquin_8x8 := Usr;
  3.      Token : Token_Type;
  4.      Done : Boolean := False;
  5.   begin
  6.      for Line in Node.Matrix'range(1) loop
  7.      for Col in Node.Matrix'range(2) loop
  8.         if Node.Matrix(Line, Col).Num = 0 then
  9.            if Col < Node.Matrix'Last(2) then
  10.           Token := Node.Matrix(Line, Col+1);
  11.           Node.Matrix(Line, Col+1) := Node.Matrix(Line, Col);
  12.           Node.Matrix(Line, Col) := Token;
  13.           Done := True;
  14.           Step := Step + 1;
  15.            end if;
  16.            exit;
  17.         end if;
  18.      end loop;
  19.      end loop;
  20.      if not Done then
  21.      raise No_Succ;
  22.      end if;
  23.      return Node;
  24.   end Right;


Code :
  1. function Left (Usr : in Taquin_8x8) return Taquin_8x8  is
  2.      Node : Taquin_8x8 := Usr;
  3.      Token : Token_Type;
  4.      Done : Boolean := False;
  5.   begin
  6.      for Line in Node.Matrix'range(1) loop
  7.      for col in Node.Matrix'range(2) loop
  8.         if Node.Matrix(Line, Col).Num = 0 then
  9.            if col > 1 then
  10.           Token := Node.Matrix(Line, Col-1);
  11.           Node.Matrix(Line, Col-1) := Node.Matrix(Line, Col);
  12.           Node.Matrix(Line, Col) := Token;
  13.           Done := True;
  14.            Step := Step + 1;
  15.            end if;
  16.             exit;
  17.         end if;
  18.      end loop;
  19.      end loop;
  20.      if not Done then
  21.      raise No_Succ;
  22.      end if;
  23.      return Node;
  24.   end Left;


 
Dans le dernier exemple communiqué ; N'apparait pas l'état suivant :
 


 1 2 3
 4 5 0
 7 8 6


Message édité par lady ada le 16-11-2026 à 10:16:03

---------------
main is business suite for Ada projects. Web site : inconito.net
n°2546143
lady ada
Posté le 16-11-2026 à 11:01:17  profilanswer
 

Pour ce cas :
 


1 2 3
4 5 6
0 7 8


 
J'ai bien :
 


1 2 3
4 5 6
7 0 8


Message édité par lady ada le 16-11-2026 à 11:01:45

---------------
main is business suite for Ada projects. Web site : inconito.net
n°2546144
lady ada
Posté le 16-11-2026 à 11:23:40  profilanswer
 

Eureka.
 
Les fonctions de mouvement ne sont pas fonctionnelles car l'instruction "exist" permet de sortir de la boucle interrieur ; Cependant, il s'agir d'un tableau à deux dimenssion et il y a deux boucles.
 
La correction choisie est la suivante, ici pour Down, à généraliser :
 

Code :
  1. function Down (Usr : in Taquin_8x8) return Taquin_8x8 is
  2.      Node : Taquin_8x8 := Usr;
  3.      Token : Token_Type;
  4.      
  5.   begin
  6.      for Line in Node.Matrix'range(1) loop
  7.      for col in Node.Matrix'range(2) loop
  8.         if Node.Matrix(Line, Col).Num = 0 then
  9.           
  10.            if Line < Node.Matrix'Last(1) then
  11.           
  12.           Token := Node.Matrix(Line+1, Col);
  13.           
  14.           Node.Matrix(Line+1, Col) := Node.Matrix(Line, Col);
  15.           
  16.           Node.Matrix(Line, Col) := Token;
  17.           
  18.           Step := Step + 1;
  19.           return Node;
  20.            end if;
  21.           
  22.         end if;        
  23.      end loop;
  24.      end loop;
  25.  
  26.      raise No_Succ;
  27.  
  28.   end Down;


 
Merci !


---------------
main is business suite for Ada projects. Web site : inconito.net

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Ada

  [Ada][Algo] Astar ; le résultat ne me semble pas conforme

 

Sujets relatifs
[Algo] Astar[Algo] Une idée pour mélanger le jeu du taquin ?
[Ada][solved] initialiser un tableau à deux dimentions[Ada][Exhausted][Redemarrage de serveur] Bloqué sur le bind
[Ada] Mécanisme de décision ou équilibre (Etude de cas : jeu d'échec)[Ada] Est-ce possible ; Comment ? (D'une chaîne, retourner un nombre
[Ada] Ada.Finalizationune technique pour découvrir Astar à l'endroit ?
[Ada] Taches et entrées de tache (traitement du clavier) 
Plus de sujets relatifs à : [Ada][Algo] Astar ; le résultat ne me semble pas conforme


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