[Algo][Résolut]Cherche algorithmes pour le Jeu du Taquin

Cherche algorithmes pour le Jeu du Taquin [Algo][Résolut] - Algo - Programmation

Marsh Posté le 09-05-2006 à 03:31:08    

:)  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  [:aldiallo]


Message édité par Profil supprimé le 07-06-2006 à 12:13:32
Reply

Marsh Posté le 09-05-2006 à 03:31:08   

Reply

Marsh Posté le 09-05-2006 à 07:42:52    

pas très claire ta phrase...


---------------
www.decouvrir-mayotte.fr www.artisandart.com
Reply

Marsh Posté le 09-05-2006 à 08:03:37    

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


---------------
Now Playing: {SYNTAX ERROR AT LINE 1210}
Reply

Marsh Posté le 09-05-2006 à 10:00:26    

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


Message édité par _darkalt3_ le 01-06-2006 à 14:37:45

---------------
Töp of the plöp
Reply

Marsh Posté le 09-05-2006 à 11:04:30    

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


Message édité par Profil supprimé le 13-05-2006 à 22:52:30
Reply

Marsh Posté le 12-05-2006 à 11:37:13    

:hello:  
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 :love:


Message édité par Profil supprimé le 13-05-2006 à 17:06:04
Reply

Marsh Posté le 16-05-2006 à 09:48:14    

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 !


Message édité par Giz le 16-05-2006 à 10:12:49
Reply

Marsh Posté le 17-05-2006 à 09:17:25    

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 :
 


Plateau de départ :
 
6 | 8 | 11 | 7  |
9 | 1 | 12 | 10 |
4 | 13| 2  | 15 |
3 | 5 | 14 |    |


 
Cas 2 :
 


Plateau de départ :
 
13| 5 | 7  | 8  |
11| 1 | 14 | 2  |
4 | 12| 10 |    |
3 | 9 | 6  | 15 |


 
Cas 3 :
 


Plateau de départ :
 
13| 12 | 3  | 15 |
  | 7  | 2  | 10 |
6 | 1  | 4  |  8 |
9 | 5  | 14 | 11 |


 
Cas 4 :
 


Plateau de départ :
 
4 | 5 |   |
3 | 7 | 6 |
8 | 1 | 2 |


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


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


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


Plateau de départ :
 
1 | 3 |
2 |   |


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


Plateau solution :
 
1 | 2 |
3 |   |


 
*) 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 ;).

Reply

Marsh Posté le 20-05-2006 à 07:41:14    

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

Code :
  1. while not Fini loop
  2.        while A_Un_Fils(Dans) loop
  3.               Passer_Au_Suivant(Dans);
  4.        end loop;
  5.        ---------------------
  6.           ajouter les noeuds suivants
  7.        ---------------------
  8.         Passer_Au_Parent(Dans);
  9.            while not A_La_Racine(Dans) loop
  10.               while A_Un_Frere(Dans) loop
  11.    
  12.                  Passer_Frere_Suivant(Dans);
  13.                  while A_Un_Fils(Dans) loop
  14.                     Passer_Au_Suivant(Dans);
  15.                  end loop;
  16.                ---------------------
  17.                   ajouter les noeuds suivant
  18.                 ---------------------
  19.                  Passer_Au_Parent(Dans);
  20.    
  21.               end loop;
  22.             Passer_Au_Parent(Dans);
  23.          end loop;
  24.      end loop;


 
je suis qu'un amateur  :heink:
a parament vous parlez de performance ; mon algo met 5 minutes a trouver un matrice 3x3,  [:666rip666]  
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  :sleep:  
 
 :hello:  

Reply

Marsh Posté le 20-05-2006 à 14:51:59    

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

Reply

Marsh Posté le 20-05-2006 à 14:51:59   

Reply

Marsh Posté le 20-05-2006 à 16:29:03    

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

Reply

Marsh Posté le 21-05-2006 à 21:51:51    

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.

Reply

Marsh Posté le 22-05-2006 à 09:36:57    

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.

Reply

Marsh Posté le 22-05-2006 à 16:14:23    

Bon, j'avous, mon algo n'est pas optimal  [:frag_facile],

Reply

Marsh Posté le 23-05-2006 à 16:00:57    

Re bonjour à tous,  :hello:  
 
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 ?

Reply

Marsh Posté le 23-05-2006 à 16:45:58    

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*.

Reply

Marsh Posté le 23-05-2006 à 17:55:02    

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 ?
 
 
 
 

Reply

Marsh Posté le 23-05-2006 à 18:01:24    

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

Reply

Marsh Posté le 23-05-2006 à 18:16:42    


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

Reply

Marsh Posté le 25-05-2006 à 08:03:40    

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


Algorithme A-étoile
 
Début
  ouverts = { état initial }
  fermés  = vide
  succès  = faux
  Tant que (ouverts non vide) et (non succès) faire
    choisir n dans les ouverts tel que f(n) est minimum
    Si est_final(n) Alors succès=vrai
    Sinon ouverts = ouverts privé de n
          fermés  = fermés + n
          Pour chaque successeurs s de n faire  
            Si (s n'est ni dans ouverts ni dans fermés)
            Alors
              ouverts = ouverts + s
              père(s) = n
              g(s) = g(n) + coût(n,s)
            Sinon
              Si (g(s) > g(n) + coût(n,s)) Alors
                père(s) = n
                g(s) = g(n) + coût(n,s)
                Si (s se trouve dans fermés) Alors
                  fermés  = fermés  - s
                  ouverts = ouverts + s
                Fin si
              Fin si
            Fin si
          Fin pour
    Fin si
  Fin TQ
Fin  


 
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
 

Reply

Marsh Posté le 25-05-2006 à 09:47:55    

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

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.         -- la, va faloire determiner L_Element_Min
  17.         if -- la j'ai pas le test je comprend plus -- then
  18.           Succes := Boolean'Value("TRUE" );
  19.         else
  20.            Supprimer_noeud(Ensemble => Dans.Ouvert,Avec => Noeud_courant.id);
  21.            ajouter(Ensemble => Dans.Fermer,Nouveau => Noeud_Courant.matrice);
  22.            for I in -- ensemble -- loop
  23.                         -- la je pense que l'algo doit varier en fonction de sont utilisation
  24.  
  25.               if not Esiste(Ensemble => Dans.Ouvert,L_Element => Nouveau_Successeur) and
  26.                 not Esiste(Ensemble => Dans.fermer,L_Element => Nouveau_Successeur) then
  27.                  -- la y a un chmilblic -- on vient de supprimer Noeud_courant de Ouvert est on doit lui ajouter un fils, c'es
  28. t louche
  29.                  Ajouter(Ensemble => Dans.ferme, Avec =>  Nouveau_Successeur);
  30.                  g(s) := g(n) + coût(n,s);  -- la je sais pas quoi faire de cette ligne
  31.               elsif (g(s) > g(n) + coût(n,s)) then -- la pareil
  32.                  Ajouter(Ensemble => Dans.Fermer, Avec => Nouveau_Successeur);
  33.                  g(s) = g(n) + coût(n,s);
  34.                  if Existe(Ensemble => Dans.Ferme, L_Element => Nouveau_success)s se trouve dans fermés) then
  35.                     -- la, je comprend plus non plus, on vient de rajouter Nouveau_successeur a ferme et on test s'il y est ?
  36.                     -- le reste, c'est pire donc
  37.                     fermés  = fermés  - S;
  38.                     ouverts = ouverts + S;
  39.                     --
  40.                     -- je doit me planter quelque part !!!!!
  41.                  end if;
  42.               end if;
  43.            end loop;
  44.  
  45.         end if;
  46.  
  47.      end loop;
  48.  
  49.   -----------------------------------------------------------------------
  50.   --                     Fin algorithme A* ou Astar                    --
  51.   -----------------------------------------------------------------------
  52.  
  53.   end Astar;

Reply

Marsh Posté le 25-05-2006 à 10:00:59    

A la ligne 17 on doit pouvoir mettre
 

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

Reply

Marsh Posté le 25-05-2006 à 11:05:05    

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

Reply

Marsh Posté le 25-05-2006 à 12:39:24    

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

Reply

Marsh Posté le 25-05-2006 à 13:57:13    

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  
 

Reply

Marsh Posté le 25-05-2006 à 15:38:53    

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;

Reply

Marsh Posté le 25-05-2006 à 16:08:04    

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

Reply

Marsh Posté le 25-05-2006 à 16:26:36    

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

Reply

Marsh Posté le 25-05-2006 à 19:36:42    

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

Marsh Posté le 25-05-2006 à 19:57:57    

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

Reply

Marsh Posté le 25-05-2006 à 23:43:09    

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

Reply

Marsh Posté le 26-05-2006 à 10:53:54    

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
 

Reply

Marsh Posté le 29-05-2006 à 10:01:27    

: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

Reply

Marsh Posté le 29-05-2006 à 12:30:23    

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.

Reply

Marsh Posté le 29-05-2006 à 12:45:57    

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

Reply

Marsh Posté le 29-05-2006 à 12:48:57    

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

Reply

Marsh Posté le 29-05-2006 à 12:59:51    


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

Reply

Marsh Posté le 29-05-2006 à 13:39:55    

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 ?

Reply

Marsh Posté le 29-05-2006 à 14:51:44    

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:

Reply

Marsh Posté le 29-05-2006 à 15:46:14    

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

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed