Reprise du message précédent :
un bon quart d'heure je crois, c'est proportionnel au nombre de matrices générées
 
mon problème doit ce situer au niveau de l'odre dans la structure Open, puisque
j'utilise le code A star que tu m'as donné, et Manhattan, que j'ai testé pure

ha ouai, 15 min ... et moi 1/3 de seconde, ... mon code est juste 3000 fois plus rapide

je vien de mesurer, c'est 24 minutes même,  
Toute façon mon code est tout pourit, c'est n'importe quoi  
Si j'essaie de faire correctement ça marche encore moins    
c'est pour ça que je jetterais bien un oeuil sur le reste de ton code,

     
 
Petit recore pour ton cas N° 1
 
j'obtien maintenant 56 deplacements, bon, toujours pas l'optimal selon toi mais,
selement 5427 matrice générées contre 19192 selon toi    
en 1 minute, toujours plus que toi main 24 fois moins que mon résultat précédent  
 
Mon heuristique est "Mahattan distance" pure, tu as raison    
 
Mon "Uniform" est le suivant

Function Uniform(Precedente,Suivante,terminale : T_Matrice) return float is
      Somme : constant Float :=
      Heuristic(suivante,Terminale) -
      Heuristic(precedente,Terminale) + 2.0;
   begin
      Return Somme;
   end Uniform;

 
Qu'en penses-tu, Giz ?
 
Edit : Même topo pour le cas N° 3
 
292445 matrices générées contre 2_005_778    
59 deplacements pour ranger la matrice contre 47    
un peut moins de 50 minutes contre 10 secondes    
 
par contre, je ne sais plus quoi faire pour trouver l'optimal, ni pour diminuer les temps de resolution  

Ouf ...
j'ai enfin trouvé l'optimal pour le cas N°1, mais en 68874 matrices au lieu de 19192

Petit record de vittesse,        
Pour le cas N°1, j'obtien 68 deplacement,certe c'est pas l'optimal
mais en 650 matrices seulement
 

 
Ecoute je ne veux pas te decevoir, mais pour une solution non optimal, c'est lamentable 650 matrices générées. Pense pour résoudre le problème non à l'optimal (juste trouver une solution) à un algorithme type depth first. Tu devrais généré au mieux ~50 matrices (moyenne des profondeurs pour une matrice 4*4).
 
EDIT : j'ai pas compris ta formule de calcul du cout uniform...tu cherches a faire quoi ?
 
EDIT 2 : en permettant pas mal de memoire a la jvm (par -Xmx512m), je suis un peu plus rapide encore car la memoire n'est saturé qu'à moins de 50% je pense donc le risque que le garbage collector s'active (ce qui coute du temps) est moindre donc il ne s'active pas (contrairement à si la mémoire est quasi pleine si je mets -Xmx128m)

Alors c'est décevant,
Bonjour Giz,
Ecoute, j'ai passé le week end a mettre mon algo dans tous les sens, et je n'est toujour pas trouvé l'equivalent de tes resultats    
j'ai bien trouvé l'optimal mais en 3,6 fois plus de matrices que toi    
Y a t-il moyen de jeter un oeuil sur le reste de ton code s'il te plait    
 

 
arf, il faut persévérer ! d'abord ne regarde pas l'optimisation (résoudre le plus vite possible), mais fait quelquechose qui marche, cad qui trouve l'optimal.
Je pense t'avoir filer le code le plus difficile : celui de A*. Il te reste à :
1) savoir générer les successeurs d'un plateau
2) savoir évaluer un plateau (son cout uniforme et son cout heuristique)
3) savoir dire si un plateau est solution ou non, auquel cas, la recherche est fini s'il est solution.
 
Franchement, c'est le plus dur que je t'ai filer en code. Courage, tu vas y arriver ! moi j'avais passé 2 week end pour faire un truc qui marche en C la première fois .
 
EDIT : si c'est moi qui te dis tout, tu n'auras aucune autosatisfaction quand ca marchera, ce qui est très démotivant .

merci Giz de t'inquiéter de mon amour propre,
 
1 : les successeur Ok, j'ai quatre fonction up,down,left, rigth qui renvoient les identifiant des voisin s'ils existent
 
2 : pour l'heuristique j'ai evalué Manhattan distance pure et Manhattan distance + le comtage des tuiles mal placées
      Et tu m'a dis d'utiliser Manhattan distance pure, ce que j'e fait
 
     pour l'uniforme j'ai evalué 1.0, 2.0 0.1 0.01 et l'heuristique de
     mon post precedant qui donne un cout relatif à la nouvelle
     distance par rapport à la précédente  
 
3 : faudrait quand même pas pousser mémé dans les ortis
 
l'optimal je l'ai, mais en 3,6 fois plus de matrice que toi
ça fait 15 jour que je suis sur l'affaire
Même si tu me donne ton code, j'aurais la satisfaction de le traduire en Ada
 
  50 matrices pour trouver une solution ça me parait un peut court quand même !!!
 
Pour l'instant, pas question d'optimisation, de toute façon je vois pas comment optimiser mon impémentation afin de rattraper mon retard par rapport à tes résultats, la difference est trop importante  
 
Malgrés mes effort, je n'arrive pas, à priori, à extraire l'élément min de Open.|
 

Tu as une liste de plateau dans Open, chaque plateau a été préalablement évalué et tu me dis que tu n'arrives pas à extraire le plateau de coup le plus petit ... je vois pas le problème la .
 
Pour le cas 1) et 2) as-tu testé les fonctions indépendamment/par débuggeur pour voir si elles marchent correctement ?.
 
Si tu as l'optimal, pourquoi as-tu alors des problèmes encore ?? ... tu peux passer à l'optimisation dans ce cas.

 
mes fonction donnant les successeurs fonctoinne, pour la distance de Manhattan, je connais suffisement l'Ada pour savoir qu'elle est juste
 
mais tu à raison je pèche un peut concernant, le coût ? . vu que ça marche pas, j'ai tout mis en doute.
 
j'ai bien trouvé l'optimal mais en 3,6 fois plus de matrice que toi, dejas qu'il me faut 200 fois plus de temps pour en générer autant, imagine

D'ailleur, j'ai toujours pas fixé uniform et c'est bien ce qui m'embete

pour le coût heuristique, tu prends manhattan distance. Pour le cout uniforme, il est de un a chaque fois que tu fais un mouvement (donc ce cout augmente de 1 pour un plateau successeur par rapport a son predeccesseur).
Donc si tout marche (tu trouves tout le temps l'optimal), redonne moi tes perf après optimisation.
Si 4*4 c'est trop long pour toi, je peux t'envoyer des tests optimaux sur des 3*3 pour verif ton prog. A toi de voir.

Oui 4x4 c'est un peut long pour faire des tests, enfin même le cas N° 1 est un peut long
 
Avec uniform = 1, je crois que j'ai tout essayé, j'y retourne quant même
 
 

wai, ben ça marche pas, y a autre chose, mais je sais quoi, que j'ai pas pigé, c'est l'élément min
Dans les publication, donc, il est ecrit : trier selon f(n) dans l'odre croissant puis selon g(n) dans l'ordre decroissant
j'ai tout essayer, et ça marche pas !
bref je recommence avec uniform = 1, ça va dejas diminuer le nombre de mes combinaisons possibles

Merci, merci Giz

au début, ton coût uniforme pour ton plateau de départ est de 0 ! (tu n'as pas fais de mouvement encore).
Pour le tri, fait le suivant f(n) seulement, ca ne changera rien sur l'optimalité. Ensuite tu peux trier sur un deuxième critère, présent que pour être plus rapide (mais non nécessaire) - moi je le fais sur h(n) et non sur g(n).

bon, et bien ça marche pas. |
donc au mieu j'ai 44 deplacement en 68874 matrices générées.

he ben c'est bon, tu as l'optimal, essaie sur les autres matrices pour voir. La rapidité de résolution dépend grandement du nombre de matrices générées...bref c'est de l'optimsation ça....
 
Indice d'optimisation n° 1 : afin d'être nettement plus performant, ne pas compter la distance de manhattan du jeton vide, mais celle de tous les autres jetons que l'on somme afin de donner le cout heuristique du plateau .

J'ai lancé le cas N° 3 hier, j'en suis a 3_000_000 de matrices générées, le but est à un peut plus de 7_000_000, le resultat demain donc
 
pour ce qui est d'esquiver le 0 dans la distance de Manhattan j'y ai déjàs pensé, penses-tu ? Et dans mon cas, ça change rien.
Je dis dans mon cas car en fait mon uniform est celle que j'ai donné un peut plus haut.
 
Par acquis de conscience, Giz, f(n) = ucost+hcost ?      

Non tu à raison, uniform = 1, ça donne le même resultat, mes plus plates excuses

 
   
 
Oui je le pense surement (déjà testé).

Ben tu pense, ou t'es sure, t'a testé, peut-etre,  
je suis surpris de la formulation de ta reponse,

Bref,
je mes resolut dans le titre du topic,
ou tu pense que je peut faire en sorte
d'obtenir les mêmes resultats que les tiens ?  

Bon, j'affine mon trie, excuse moi Giz, je suis pas très fort,
 
j'ai reussi à descendre à 27112 matrice générées, toujours pour un compte optimal de rangement

 
OK, et t'arrive à résoudre mes trois exemple à l'optimal ?
Je disais que je suis sûr que de ne pas compter le 0 permet d'avoir de meilleur résultats (plus rapide).

 
Bonjour Giz,
 
ben, j'ai lancé le cas N°3, j'attend les resultats,
 
Quant a l'esquive du 0 dans Manhattan distance, dans mon cas, ça n'a pas beaucoup d'effet    
 
Pour l'instant mon meilleur resultat pour le Cas N°1
est 44 deplacement, ok, et 25957 matrices générées
j'ai pas encore réussi à descendre en deça

 
Ben pour le nombre de déplacements, j'espère que tu n'arriveras pas à descendre en dessous (sinon mon algo est faux ). Pour le nombre de matrice générés, tu peux améliorer encore (toujours d'après mes résultats).
Si tu désires, je te donnerai demain des jeux de tests sur d'autres matrices 3*3 pour bien voir si ton optimalité marche (ce qui reste le plus important)

Si tu as des matrice 5x5, je suis preneur aussi  

 
impossible à résoudre à l'optimal avec A*. Faudrait que je lance la résolution pendant plusieurs heures avec RBFS pour trouver l'optimal . Ca 'tintéresse vraiment des 5*5 ?

oh que oui, ça m'interresse,
il faut que je verifie que l'algo est valable pour n'importe quelle taille de matrice !!!  

très bien, as-tu une matrice 5*5 pour laquelle tu as une solution ? qu'on vérifie sur la même (passe moi motif de départ et d'arrivé)
 
NB : c'est bon, j'ai corrigé et je gère maintenant n'importe quelle matrice d'arrivée .

je te propose de jouer avec celle-ci, pas trop melangée
 
10|24|22| 3|20
---------------------
12|  2|  1|15| 5
---------------------
17|13|  0|18| 7
----------------------
11|  9|19|  6|16
----------------------
  4|23|21| 8|14  
 
la matrice cible est une matrice ordonnée de gauche a droite/ de haut en bas avec zero central (en 3.3)
est-ce ok ?

A wai, j'ai pas encore la solution mais j'espere que ça va pas tarder !!!

OK, mais mefie toi certain problème sont insolubles...
 
RQ : ok pour la cible :
 
1 2 3 4 5
6 7 8 9 10
11 12 0 13 14
15 16 17 18 19
20 21 22 23 24

j'aime pas quand tu dis ça    
 
pour moi un Taquin insoluble, c'est un taquin qu'on aurait demonté et remonté n'importe comment !!
Si c'est ça que tu veut dire, alors d'accord,
 
et si tu crois que je t'ai envoyer n'importe qu'elle matrice,
sache que je melange les tuiles avec les methodes down up left et right que j'utilise pour ranger les matrices,  
 
on est ok sur l'exo 5x5,
j'ai lancé mon algo le plus rapide dans un premier temps pour avoir une idée de l'e/ampleur du problème !!

Insoluble ca veut dire qu'il n'existe pas de chemin possible pour arrivée au plateau de fin en partant du plateau de départ. Lancé ton algo le plus rapide certes, mais faut être sur d'avoir l'optimal sinon, même une matrice 5*5, ca se résoud rapidement ! Moi je vais chercher à le résoudre à l'optimal.

Bonjour Giz,
je n'ai toujours pas de resultats pour la matrice 5x5 ce matin,
j'ai pris un peut de retard hier soir parce que j'ai à nouveau chercher à diminuer
le nombre de matrices générées par mon algo et je n'ai gagner que 33 matrices pour le cas N°1.
Alors ce matin j'ai encore trois questions : utilises-tu un algorithme "branch and bound" ?
Si non, quel startagène à tu mis en place ?
 
Moi j'ai beau trier par f(n') Ok, puis par g(n') ou h(n') (c'est egal en fait) j'obient toujours 25957
25924 maintenant que je supprime les doublons dans ma liste Open
 
Si tes reponse à mes question sont non et aucun,  
vu que nous sommes sensés avoir le même algorithme,  
d'une part, je vais continuer a chercher du côté du trie, mais je crois que c'est rapé
d'autre part, j'envisage de metre en place une sorte de "branch and bound" mais je n'ai aucune idée
de "comment determiner si une branche est interressante ou non" ?
En as-tu une idée ?