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

 
Moi non plus. J'ai lancé la résolution hier soir vers 19h. Ce matin juste avant d'aller au boulot (8H00) ca tournait toujours. Mais très honnêtement, même avec RBFS, je n'ai aucun espoir, ce sera bien trop long.
 
 
 
Ben A* est un algo de type branch and bound. L'idée de cet algo est de borner les choses. Dans le cas de A* nous disposons d'une borne inférieure seulement disant "Je suis sûr que si je pars sur cette branche, la solution trouvée, sil y en a une, coûtera AU MOINS tant.". En général les bons algo branch and bound utilise aussi une borne supérieure disant "Si le coût estimé est supérieure à la borne sup, alors couper cette branche" Ces idées de bornes permettent de couper des branches de l'arbre...et de manière de plus en plus significative que les bornes sont précises (cad qui fournissent un petit intervalle). Cependant dans A* nous pouvons pas utiliser de borne supérieure car la stratégie de développement de l'arbre est de type "Best first" et cette stratégie garantie déjà le développement minimal de noeud. Pour améliorer la rapidité, il faudrait fournir une borne inférieure de meilleure qualité que manhattan distance... mais je ne vois pas laquelle (personne d'ailleurs)
 
 
 
 
Oui tout a fait c'est égal (je l'ai aussi expérimenté).
C'est vrai que disposant du même algo , nous devrions disposer des mêmes résultats .

Alors il me reste une chose à élucider::=
 
Sur www.fortunecity.com, il est ecrit

 
Quest-ce que veut dire "avec priorite aux etats terminaux." ?    
 
Merci Giz pour tes reponses    

"priorité aux états terminaux" ca veut dire "priorité au développement des feuilles les plus profondes dans l'arbre" ce qui est le second tri selon g(n). Cette logique part du principe suivant (qui est tout à fait juste) "plus un noeud est profond, et plus on est proche de la solution, donc donnons lui la priorité"...à noter que ce raisonnement s'applique de même si on fait un second tri sur h(n) (celui que je fais)...et les résultats en perf sont les mêmes pour ce problème.

21748     , voila une amelioration notable, mais toujour pas les 19192 espérés
peut-etre, cet apès midi, serais-je mieu inspiré  

En y refléchissant, je ne pense pas pouvoir faire mieu et je pense que le problème est du au fait que j'utilise une liste chaînée au lieu d'un arbre
C'est pourquoi Giz, j'ai encore quelques question ...  
Comment compares-tu les éléménts de ton arbre ?
Utilises-tu un simple arbre binaire ou bien un p-arbre ou n-aire ?
 
Je te pose ces questions, mais je sais vraiment pas si j'exploiterai les reponses vu que je maitrise vraiment pas les arbres !!
 
 
 

Le coup de la liste chaînée, je m'y attendais pas...c'est clair que c'est pourri. Si tu n'utilises déjà même pas les bonnes strutures de données, alors oublie l'optimisation. Elles influent à 80% sur la rapidité de l'algo. Ensuite vient le second tri qui influt à 15% puis 5% le reste (astuces de développement).
Donc pour comparer les éléments de l'arbre, faut utiliser la struture de données "File de priorité" ou "Tas de fibonnacci". Ce sont des strutures qui permettent d'extraire l'élément min d'un ensemble en O(1) (instantané). L'insertion et la suppression se font en O(log(n)). Donc la tu obtiendras des perf au pire en O(log(n)) alors qu'avec ta liste chainée tu étais en O(n) pour la recherche de l'élément min déjà.
Si tu veux te coder ces structures de données, bonne chance   moi j'utilise celles de Java.
 
 
RQ : j'ai edité mon message précédent de "priorité au développement des feuilles de l'arbre" en "priorité au développement des feuilles les plus profondes dans l'arbre" ... car dans open ce sont que des feuilles.
 

 Zut alors, Java fournit des gestionnaires de données ! Premiere grande nouvelle de l'année !!    
 
 je sort un peut du sujet, excuse moi Giz pour mon ignorance s'il te plait    
 
je connais trois grandes classes de gestionnaires de données ::=
 
les files
les arbres
les piles
 
y en a t-il d'autre ?  
 
 
est-ce que les files de priotités appartiennent à une de ces classes ? ... ; une file ou un arbre ?
si tu me parles de feuille, c'est que tu parles d'arbre !!
la oû je comprend plus, c'est quand tu dis qu'il n'y a que des feuilles dans l'arbre qui implémente la file de priorité, car dans ce cas, c'est une file    
Comme sont non l'indique je m'attend à ce que tu me réponde c'est un file, dans ce cas, je vois pas la difference avec ma liste chainée.
Dans le cas contraire, un arbre est un arbre
 
   
 
5 minutes et je met mon implémentation en ligne ICI
 
Tu peut matter le type de Open, qui est le même que Close d'ailleur, dans p_taquin.ads. C'est le type T_Ensemble.
Seul les procedure dinsertion et d'extraction different, Add et Poll pour Open et Put et Get pour Close sont implémentées dans p_taquin.adb
Je sais, c'est du mauvais travail  

Il y en a plein de strutures de données ... => http://www.nist.gov/dads/
 
Les files de priorités peuvent être implémentées par tableau ou arbre (comme je les connais), regarde sous google pour plus d'info.
J'ai dis que la liste open ne contient que des feuilles de l'arbre de recherche.

Je parle pas l'english    
si tout ça ou presque, ce sont des gestionnaires de données .................................  
bref.|
 
Ok alors comme ça, oui euhhh, y a un arbre et une liste,
je comprend de moins en moins    
 
je vais refléchir à ce que je peux faire !!
 
Merci Giz      
 
Enfin bon c'est pas mal quant même je trouve,
j'ai pas trop galéré pour traduire A* du Java à l'Ada,
moins que pour trier ma liste Open qui n'est toujours pas parfaite
 
Pour ce qui est des temps, de toute façon mon programme rame dés les premières matrices
je ne pense pas que la difference se situe uniquement du côté de la structure d'Open qui est quand même pas mal trié je trouve.
 
dans quelque jours, un fois que j'aurais résolut la matrice 5x5   , je testerai le programme sous Windows

 bonjour,
 
je suis embété, je me suis acheté un bouquin pourtant, mais je ne comprend toujours rien au Files de Priorités
 
j'ai donc encore besoin d'un peut d'aide  

Giz,
Je suis en train de mater mon prog et il y a un truc louche,
j'en suis à 2600000 matrice généré et ucost est compris entre 24 et 50
 
est-ce normal    
 
grosso modo 25 tuiles x4 deplacements x 50 = 5000 pas 2600000,  
 
Merci !!
 
Reedit : bon, c'est p'tet pas comme ça qui'il faut compter, n'empeche que je trouve ça louche !!
 
Rereedit : IMPORTANT Giz, est que tu veut dire que quant tu fait un Add il faut garder que les feuille prioritaire ??? Rerereedit :: non c'est idiot ce que je te demande  

Bonjour,
 
j'ai réfléchi à ce que j'étais capable de faire pour la gestion de l'ensemble Open de l'algo A*
Voila, j'ai l'intantion de construire un arbre et d'importer les feuille priorirataires dans un tableau
 
vous en pensez quoi,
 
et toi Giz t'en pense quoi, de ma superbe idée  
 
finalement c'eszt peut-etre la bonne structure d'un file de priorité

Pour la matrice 5*5, je n'arrive même pas à trouver UNE solution. Même avec 1.5Go de memoire, je n'ai pas assez.

en fait je bloque encore sur le cas N° 3 de tes matrice 4x4

4363003 matrices générées pour resoudre le cas N°3

hum...c'est beaucoup ça   . Et pour les 2 premiers cas, tu trouves comme moi ?

Pour le premier 21748 donc, le deuxieme je ne l'ai pas lancé encore