Reprise du message précédent :
Bon, ben fausse anonce, ça marche toujours pas,
pour une matrice 2x2 pas de probleme    
 
A+

Quasiment 5 minutes pour resoudre un matrice 3x3 sur un Pc    
 
L'ago,  
 

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;

 
A la rechereche de doublons
 
Comme aujoud'hui c'est dimance je me lance a la recherche d'un algo pour revisiter mon arbre afin de determiner si une matrice a dejas des enfants dans l'arbre, histoire de minimiser un peut la consomation de la mémoire.  
il s'agit de revisiter un arbre n-aire peut-etre un peut particulier puisque je l'ai conçu moi même, sans me conformer a un standard.
 

-- retourne VRAI si l'on trouve la matrice dans les noeuds des etages supperieurs, faut si non. 
 function Dans_Les_etages_supperieurs(Dans : T_Arbre; Matrice : T_Matrice) Return Boolean;

 
les sources de Taquin_9 sont toujours dispo ICI
 
je pourrai lancer un truc du genre, le premier qui trouve l'algo gagne un boutielle de champagne, mais je me tate,  
... aller bon c'est ok, une bouteille de champ au gagnant  

Voila pour la recherche de doublons, l'algorithme est quasiment le même que celui utilisé pour la creation de l'arbre . Avec cet algo j'ai divisé par 100 le nombre de matrices générées pour trouver une solution dans une matrice 3x3. j'ai lancé hier soir la resolution d'une matrice 4x4 au par avant impossible a resoudre avec mon PC (trop peut de memoire), j'attend les resultat. En tout cas c'est lent    
 

Hey, how do you do ?
 
J'ai lessé tomber ma resolution de matrice 4*4 apres 18 heures   , 500_000 matrices générées, le programme ramait lamentablement.
 
Je suis donc obligé, de m'attaquer à d'autres algoritmes, de vrais algos.
 
C'est donc à l'algorithmes A* que je décide de m'attaquer.

et déjàs, j'y comprend qu'dâle, enfin presque. Y a du taf.
 
J'aurai grand plaisir à partager le travail, non pas pour en faire moins mais pour avoir la contrainte de travailler en equipe, ce qui me pousserai à faire un travail peut-etre un peut plus carré.
 
La page complete au j'ai trouvé l'image ci-dessu L'algorithme A*
un autre lien vers l'algorithme A* Taquin ameliore
 
Voila, y a plus qu'à    

je me repete un peut, c'est pour la bonne cause  
 

Source : Chemins optimaux
 
Wikipedia de l'algorithme A*

j'ai faï oublier cette superbe page sur le sujet Implémentation de l'algorithme de Dijkstra algorithme duquel dérive l'agorithme A*

Un autre speudo-code de l'algorithme A* ou A star,  
 

Encore un speudo-code de l'algorithme A* ou A star
 

 
plus ça va, plus c'est plus pire  

Le pire c'est quand même celui-la

 
mais je kif sur celui-la    
 

 
Ce dernier est une variante "recherche en profondeur" de l'algorithme A*
 
mais on puet lire dans Résolution de problèmes en Intelligence Artificielle

 
Alors bon, va comprendre Charles  

 
 
Encore de l'algorithme A*, ce serait plutôt ça forme mathematique
 
Principe général : évaluation du coût
total d’un sommet
 
Coût total (F) = Coût depuis la source (G) +
Coût vers la destination (H)
 
ß G : Coût depuis la source
° Algorithmes classiques (Ford, Bellman, Dijkstra)
° Gi = min Gj+ Cij / i prédecesseur de j
                                Cij coût de l’arc (i,j)
ß H : Coût vers la destination
° Difficile puisque le reste du chemin (vers la
destination) est encore inconnu.

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

 
 
Ben en fait courant est null alors c'est normal que ça plante    
Tout ça a cause de mes calculs de distances, c'est n'importe quoi  
en plus je les ai afficher pour voir leur poids, ils sont fauts    
je retourne voire que quoi il en retourne    
 

Finalement c'est à peut près "juste", j'avais mal compris ce que le m'expliquais à moi même
j'ai mis juste entre guillemets parce que c'est encore mon code perso et pas les distances réelles
 
je programme tourne un peut, je resouds, surement pas hazard, une matrice / trois
 
 
mais maintenant j'ai un problème avec un := new T_Type ' (null,val); qui lève Constraint_Error
 
un := new qui lève constarint_error, ça dis quelque chose à quelqu'un à cette heure ci ?
 
Merci

Ba, j'ai trouvé, merci à ceux qui planche

 
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,
Comme aujourd'hui c'est dimache .... je vous l'ai déjàs faite peut-etre    
 
je disais donc, comme demain c'est lundi, et que je voudrais pousser personne au travail    
 
je vous propose, en cette belle journée de printemp,
de vous pencher, sans tomber, sur la manière d'obtenir une liste chainee, triée selon plusieur critères,
Deux en fait, dans mon cas ... c'est pour la liste Open de l'algorithme A Star
 
Voila, je ne sais pas si ça vaut le coup d'ouvrir un nouveau topic ?
 
j'ai deux clefs par element, Hcost et Ucost et je doit maintenir
une liste trier dans l'odre croissant selon une clef et decroissant selon l'autre clef
 
Je suis dans le cas oû les clefs ne sont pas uniques
 
exemple :
A 9
A 5
A 3
B 7
B 5
B 2
C 3
C 1
 
 
J'ai une procedure de trie-fusion, que j'ai utilisé succesivement avec les deux critères
mai je doit obtenir un truc dans ce genre
 
A n
A n
A n
B n
B n
C n
C n
 
 au premier trie,
 
et
 
X 9
X 7
X 5
X 5
X 3
X 3
X 2
X 1
 
 après le second trie
 
donc voila, comment trier, ou maintenir une liste triée selon 2 criteres ? tel est ma question
 
Bonne journée,
Bonne continuation
 
 
   

Voila, j'espere, la moitié d'un reponse à ma derniere interrogation,
comment obtenir un liste chainee triée selon deux criteteres ?
 
Pour trier, je ne sais pas trop, mais pour maintenir, voila ce que j'ai fait
 

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.hcost <= Courant.hcost then
            if Ptr.ucost > Courant.ucost then
               Precedent := Ensemble.Tete;
               Ensemble.Tete := Ptr;
               Ptr.Suivant := Precedent;
               Ensemble.Longueur := Ensemble.Longueur + 1;
            else
               Ensemble.Tete.Suivant := Ptr;
               Ensemble.Longueur := Ensemble.Longueur + 1;
            end if;
         else
            Ensemble.Tete.Suivant := Ptr;
            Ensemble.Longueur := Ensemble.Longueur + 1;
         end if;
      else
         while Courant.Suivant /= null and then -- parcours selon un critere
           Ptr.hcost > Courant.hcost loop
            Precedent := Courant;
            Courant := Courant.Suivant;
         end loop;
         while Courant.Suivant /= null and then -- parcours selon un deuxieme criteres
           Ptr.ucost < Courant.ucost loop
            Precedent := courant;
            Courant := Courant.Suivant;
         end loop;
         if Precedent = null then
            raise Program_Error;
         end if;
         Precedent.Suivant := Ptr;
         Ptr.Suivant := Courant;
         Ensemble.Longueur := Ensemble.Longueur + 1;
      end if;
   end Add;

Des boucles successives de parcours de la chaine avec des criteres de comparaison differents

 

 
Et bonjour,
 
j'appelle au secour, ...
 
j'ai un bug monstrueu dans mon implementation de l'algorithme A star
 
dans la fonction existe qui renvoie vrai si la matrice existe dans une liste chaînée, faut si non
 
et bien vouz savez quoi ... courant.suivant n'est jamais null  
autrement dit la liste est infinit
 
alors j'ai mis des .suivant := null; dans mes procedure d'extraction et d'insertion, poll et put, la source et la destination
 
d'ou mon appel au secour
 
la fonction existe, est tout ce qu'il y à de plus classique
 

function Existe (Ensemble : in T_Ensemble ; L_Element : T_Matrice) return Boolean is
          Courant : T_Ptr_Place_Ensemble := Ensemble.Tete;
       begin
          while Courant /= null loop
             if Sont_Egales(Courant.Matrice,L_Element)  then
                return True;
             end if;
             Courant := Courant.Suivant;
          end loop;
          return False;
       end Existe;

 
Quelqu'un aurait-il une idée de l'erreur ?
 
le reste des source de Taquin_14 est disponible ICI

Un autre monstruosité pendanss qu'on y est
 

Count_Mal_Places : T_Borne_2 := T_Borne_2'Last+1;

 
et ça compile, et ça compile, et oui,    
 
elle est bonne, non        

 
   
 
Donc, voila, la deusième version, plus serieuse que la première, est presque terminée, Merci à Giz
j'ai utilisé dans cette deusième version pour resoudre le jeu du Taquin l'algorithme A* ou A star et la distance de Manhattan
j'ai ouvert un topic dans la categorie algo
 
il me reste c'est deux problèmes à resoudre,
 1 : je ne peut pas passé mon instance de integer_io.put en parametre de genericité de p_mon_appli_taquin à p_taquin      
       le compilateur dit ::=

 2 : ma liste Fermés/Close est circularisée, elle ne devrait pas l'etre      
 
les sources de Taquin_14 sont toujours disponibles ICI
 

Bon, et bien finalement, c'est le boxon
 
En effet, j'avais fait une erreur, j'ai revue ma copie, essayant de me confrmer au publication sur l'algorithme A*,
Mais bizarement les performances sont moindres que celles obtenues l'orsque qu'il y avais des erreur ?
 
Alors je sais plus quoi faire,
 
Est-ce qu'un peut de desodre serait-il bénéfique à la resolution du taquin ?    
 
je repart donc dans la cat algo pour élucider l'affaire

 
=> Erf t'es trop rapide à la reflexion

bonjours
 
j'ai dejàs ecrit dans mon topic Algo, mais comme c'est un implémentation Ada que je veux
 
Ce sont les Files de priorités que je souhiterai aborder ici,
En effet, pour implémenter le gestionnaire de donnée de l'ensemble Open de l'agorithme A*,
j'ai choisi une liste châiné, hors celle ci s'avere etre innadapté au probleme.
 
Sur les conseils de Giz, je souhaiterai implémenter une File de priorité avec Ada.
Seulement je comprend rien à ce qu'est une file de priorité,
surtout que, apparement, mon ensemble contient des doublons, pourtant differant, ou alors les element ne sont pas comparable.  
Enfin bref, je reformule plus concretement
 
J'ai besoin d'une file de priorité pour l'ensemble Open de l'algorithme A* appliqué au jeu du taquin.
 
 
 

  Bonjour à tous,
Toujours pour ma file de priorité, j'étudie la structure arbre de recherche, et je suis pas fort en arbre  
Est-ce que qu'elqu'un serait inspiré par un arbre binaire de recherche maintenu trier selon deux critère ??  
je ne sais pas si c'est possible ??
Enfin bref, c'est pour une file de priorités, avec Ada bien sure ! !
 
Merci, merci !!

j'ai fait un arbre qui marche pour une matrice 2x2, c'est pas mal déjàs    
je vous passe le code  

 
Défois, que certains ne s'interressent aux offres d'emplois,
je réitère mon offre dans le topic
 
je suis planté, parce que je connais rien ni aux files de priorités, ni au tables de hachage, ni aux abres d'ailleur    
 
je propose
200 Euros pour une implèmentation d'un gestionnaire de données pour l'ensemble Close de l'algoritme A* exploité dans le cadre d'un projet de developpement d'un programme de résolution du jeu du Taquin, apriori, une Table de hachage
 
300 Euros pour une implémentation d'un gestionnaire de données pour l'ensemble Open de l'algorithme A* exploité dans le cadre d'un projet de developpement d'un programme de résolution du jeu du Taquin, apriori, une File de priorités

Topic Annonces d'emplois
 
Merci à ceux qui planche    
 
A part ça ben, justement mon implémentation ne marche pas terrible,
j'ai des problème pour résoudre un matrice que Giz m'a donné dans le topic algo
j'aurais du générer un peut plus de 2_000_000 de matrices, j'en suis a 3_000_000
et j'ai pas la solution, Blem    
 
 
 

Je viens de trouver une info pour l'ensemble Close
A priori, il existe un paquetage Ada, Ada.Containers qui implémente une table de hachage
le problème la, c'est que j'ai pas cette librairie dans ma distrib Debian
 
Si quelqu'un pouvait me faire un petit tgz ou un zip du paquetage Ada.Containers et de ces fils ...
Merci
 
 
edit : Au zut, en fait je l'ai vous derangez pas, excuses

Désolé pour ceux qui aurais sauté sur leur zipeur !!
Heureu d'apprendre qu'il existe une version 2005 d'Ada    
Malheuresement je ne pense pas pouvoir utiliser ces implémentations de containers de cette nouvelle version    
 
 

 
 
Re bonjour à tous
 
D'abord, pour qui ça peut interresser, je viens de faire une mise à jour (de bosser un peu) de mes deux implémentations du jeu du Taquin sur denimes.net à http://denimes.net/des_prog/Taquin/index.html.
 
 
je suis toujours à la recherche de tuyaux, d'aide, de sous traitant pour implémenter une file de priorités et une table de hachage avec Ada (j'avais une adresse mais je l'ai perdu). Ces gestionnaires de données doivent etre adapté à l'algorithme Astar.