Reprise du message précédent :

 
Je donne ma langue au chat    
 
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  

indice 2 : utilise un tableau pour représenter le plateau. Ex : [1, 3, 5, 7, 8, 2, 4, 6, X]. En partant de la valeur du tableau dans une case et de l'indice correspondant à cette case tu arrives à déterminer Où la valeur (le jeton) est et où il doit être => et donc tu peux calculer la distance de manhattan à partir de là (le signe - peut être nécessaire en fait).

Pardonne moi d'avance, Giz, je suis peut-etre dans l'erreur, mais je calcule déjàs la distance de Manhattan
en faisant la somme des sommes des differences entre les absisses des matrices courante et terminale et
 des differences entre les ordonnees des matrices courante et terminale,
 
Enfin bref ça doit revenir au même, mais ça marche pas, alors je vais faire un tableau 1d pour voir
 ....
 .....
 .....
Un peut plus tard à Nîmes,
 
Et bien ça ne marche pas mieu avec une comparaison dans un tableau 1d, c'était à prévoir
Y a un hic quelque part    
 
 
Comme je suis assé sur de moi sur le coup de la distance de Manhattan
je me demande si j'ai bien implémenté l'algo A star,
si oui alors je pourais en deduire avec certitude que la distance de Manhattan est insuffisante à la resolution
d'un Taquin même 3x3,
 
Quand je pense que tu resouds, Giz,  un Taquin 4x4 en moins de 10 secondes .... Mais comment fais-tu ?
 
je met les sources Ada de Taquin 14 à disposition ICI
l'algo A star est implémenté dans p_taquin.adb

Avant de coder l'algo A*, il serait bien d'apprendre à savoir coder le problème   . Coder un problème ne dépend pas de A*. Coder le problème (savoir établir ses successeurs et evaluer un plateau) est indépendant de la méthode de résolution, hein   .
 
Indice 3 : une heuristique admissible plus facile à coder alors est compter le nombre de pièces mal placées. (entre 0 et 9 pour u taquin 3*3). Et ca dis moi pas que tu n'y arrives pas...

 
Bonjour Giz,
Pourquoi dis-tu que je n'y arrive pas, je calcul la distance de Manhattan, je compte les pièces mal placées sans problème à priori
quant au successeur je les connais tres bien, je melange judicieusement mon Taquin avec
 
Mais Manhattan ne suffis pas, j'en ai la preuve !!
 
0|7|X
8|X|X
X|X|X
 
le zero est l'element vide et est à ça place,
7 et 8 sont ces unique successeur, et leur permutation augmente la listance de Manhattan
Alors, effectivement il faut tirer sur la corde ce se placer deans une situation pareil, je ne sai pas si elle est valide, apriori oui
 
pour mon calcul de distance, j'en suis, simplement a cumuler la distance de Manhattan et le nombre de piece mal placées
mais soit ça suffit pas, soit j'ai une erreur dans A star

Et voila, pour les matrices 3x3 en tout cas, cette fois je croix que je tien le bon bout
 
Au lieu de trier les elements selon leur distance au but d'abord puis selon leur distance a l'initiale en suite,
comme il est prescrit dans certaine publication, je trie les elements selon la somme des distances
 
Giz, dis moi si je me trompe    
 
donc a par les cas particulier comme celui dont je parle dans mon message precedent, ça marche
pour les matrices 3x3. Temps de resolution ~= 45 secondes (sur un pc mono proc 2.6 GHertz), nombre de matrice générée ~= 1400, nombre de permutation pour arriver au but 19, alors que le nombre de mouvement efefctué pour le melange est ~= 200
 
Voila pas mieu pour le moment, j'attend les resultat sur une matrice 4x4,

ben voilà, t'a fini par y arriver alors. Donne moi ton plateau de départ et ton plateau d'arrivé, que j'observe mes résultats avec .

un plateau de depart,  
 
3|2|6
8|7|4
0|5|1
 
 
plateau d'arriver
 
1|4|7
2[5|8
3|6|0
 
 
23 coup pour le ranger

et les résultats du benchmark stp...

j'ai une matrice  4x4 aussi ...      
 
Plateu de depart
 
13| 9| 8| 1
 6|14| 2| 7
 5|11|0 |15
 4|10|12|3  
 
PLateau d'arrivé
 1| 5| 9|12
 2| 6|10|13
 3| 7| 0|14
 4| 8|11|15
 
en 61 coups
 
 
je lance 5x5 maintenant, pour voir mais je crois que j'ai trouvé la difference entre les matrices de différentes taille,
 

 
  , je n'ai jamais réussi à trouver des solutions s'y profonde !! (combien de temps mets-tu et combien de mémoire ça te prends ?)
...si 61 coups est bien l'optimal, chapeau mec !    
Si ça marche avec 5*5, alors là, tu fais mieux que moi !  

 
je te donne un autre plateau pour lequel j'ai le nombre de plateau généré mais je peut faire varier ce nombre,
je n'ai pas encore trouvé l'optimal Manhattan*((N*M)/2) ou Manhatan*(((N*M)/2)-1) ou un autre , je sais pas encore
 
Nombre de Plateau généré avec heuristic = Manhattan*((N*M)/2) + count_mal_placés == 1800
 
Plateau de depart
 
7|5|3
1|6|2
8|4|0
 
Pateau d'arrivé
 
1|4|7
2|5|8
3|6|0
 
Nombre de deplacement 27

POur la memoire, je sais pas, pas baucoup à mon avis pour un ematrice 3x3 ou 4x4 même, apres sa doit etre proportionnel
pour les temps, pour une matrice 3x3 ou 4x4 c'est le l'ordre de 30 à 50 secondes
 
je lance 5x5

ououps ..    
 
j'ai dis une bétise avec Manhattan*((N+M)/2) ou Manhatan*(((N+M)/2)-1)
 
ça devrais suffire

 
    ... en sommant les 2 heuristiques, tu n'obtiens pas une valeur heuristique admissible   => ta solution n'est pas optimale !

 
Pas la peine de mexpliqué, je comprendrai pas
 
Mais 5x5 avec Manhattan*((N+M)/2) + (count_mal_places*((N+M)/2))-(M+N)/2 ça marche
 
Maintenant pour te dire si c'est l'optimale   je sais pas
 
Est-ce que tu fais mieu ?
 

Je te dirai ça dépend demain, le temps que je passe chez moi...mais la matrice 4*4, je ne les résouds pas toutes.

Bon en fait, j'ai pas pu prendre ton plateau d'arrivé car le mien est codé en dur dans le code et j'ai pas envie de me replonger dans le code. Donc si tu prends le même plateau d'arrivé que moi (de 1 à n puis 0 en allant de gauche à droite et de haut en bas), pour ton 1er problème 3*3, je trouve aucune solution réalisable et pour ton plateau 4*4, je n'arrive pas à le résoudre avec A* (avec 1Go de ram autorisé pourtant).

Bonjour Giz,
Bain, moi aussi c'est codé en "dur", mais je vais voir ce que je peut faire !
 
Pour ce qui est des resultats, et bien je revoie ma copie,
En effet, pour les matrice 3x3, la resolution est de l'ordre de la minute,
               pour les matrice 4x4, c'est plutot de l'odre de 10, 12 minutes pour la derniere que j'ai lancé, pas tres mélangée non plus
               pour les matrice 5x5, j'ai lancé 5x5 hier soir, il y à 14 heures, je n'est toujours pas la solution
                                                    avec une ocupation memoire de 351 Mo et 2_000_000 de matrices générées
                                                    mais ça tourne
                                                    malheuresement, je crois que "uniform" ne sera pas suffisament discréminant par rapport a la complexité du mélange et de "heuristic"
                                                    je vais donc etre obligé de recommencer le test
 

 
j'ai peut-etre dis une betise encore  

une matrice 3x3 dont l'ordre est celui que tu m'as specifié
 
6|4|5
1|0|7
8|3|2
 
Nombre de matrices générées ~= 2_500
Temps de resolution  ~= 33 secondes
Nombre de deplacement pour ranger cette matrice = 29
 
 
une matrice 4x4 dont l'ordre est celui que tu m'as specifié
 
  6|  1|  7|  8
12|13|10|14
  4|  5|  9 |  0
11|  2|15|  3
 
Nombre de matrices générées ~= 60_000
Temps de resolution  ~= 10minutes
Nombre de deplacement pour ranger cette matrice = 80
 
Il y a un autre parametre qui rentre en compte dans la resolution,
c'est l'ordre dans lequel tu donnes les successeurs
 

 
 
et une matrice 5x5 dans la boite            
 
Occupation memoire ~= 351 Mo
temps de resolution ~= 15 heures
Nombre de deplacements = 135
Nomre de matrices généré un peut plus de 2_000_000
 
c'est pas la peine que je te la donne, les lignes est colonnes sont inversé
 
Giz,
maintenant je peut me lance dans l'implementation d'une procedure de lecture de matrice dans un fichier
pour je puisse tester les matrices que tu ne parviens pas à resoudre, si tu les as conservé ?

ouai, vas-y affiche moi la solution des problèmes insolubles que je ne résoud pas que je rigole pour voir . 135 déplacements ... c'est impossible de descendre à cette profondeur tout en ayant l'optimal

 
J'ai pas compris ce que tu veut ?
 
Donne moi une matrice !
 
Ce soir je lance une autre matrice 5x5 avec pour uniform, seulement Manhattan, pour voir
 
Mais donne moi une matrice, soluble, que tu ne resoud pas avec ton algo !
 
edit : je voulais dire : avec pour heuristic, seulement Manhattan, pour voir

plateau de depart,  
 
3|2|6
8|7|4
0|5|1
 
 
plateau d'arriver
 
1|2|3
4[5|6
7|8|0  
 
Affiche moi la solution de ça .

 
 
Je suis en train d'essayer de le faire à la main et je pense que le cette configuration est tout simplement impossible !  

et ton programme, il sert à quoi ... sinon effectivement, mon programme ne trouve pas de solution non plus .

Comment ça, il sert à quoi ?
A resoudre un jeu de Taquin !!
pourquoi, le tien sert-il à autre chose ?
Moi en fait, c'est pour pas perdre la main en programmation, je me lance de petit défit
je doit dire que sans toi, j'y serai peut-etre pas arrivé
En tout cas je trouve cet l'algo A* formidable, une ingeniosité
j'ai pris grand plaisir a le traduire du Java en Ada, ton code est super propre
 
Il me reste tout de même deux detail a resoudre,
 1 : j'ai un probleme de liste chaînée infinit, courant.suivant n'est jamais nul    
et 2 : il me manque un ou deux elements dans ma liste solution    
 
par hasard, tu n'aurais pas des symptomes similaire ?

tu disais que tu le résolvait à la main, fait la résolution avec ton nouveau programme et donne la solution.
liste chainee infinie....sache que  
1) je n'utilise pas de liste chainee
2) infini c'est impossible sinon tu exploses la mémoire ! ... donc ton codage d'ajout/retrait dans la liste est mal foutu.
 
Ta liste solution doit etre parfaite (commence par le plateau de départ et se termine par le plateau d'arrive).
Moi je n'ai aucun problème.

J'ai bien lancé ta matrice avec mon prog mais la liste Fermés augmente plus vite que la list Ouverts,
je suis pas sur que ce soi anormal mais ce comportement differe de celui observé avec d'autre matrice,
je l'ai lessai tourne 30 minutes.
 
consider que 1 pointe sur 2 et 2 pointe sur 1 on à bien un liste circulaire et donc une iteration infini
Dans mes procedures Poll et Get je fais un Ptr.suivant := null ; normal, mais ça marche pas.    
 
Pour ce qui est du dernier élément, ça y est, je l'ai trouvé    
 
Si tu veux d'autres matrices, plus ou moins melangées ....
 
 

Giz, bonjour,
 
pourais-tu me donner ton heuristique pour je jeu du taquin, si elle differe de la miènne,
 
pour l'instant j'en suis a heuristic = Manhattan*((N+M)/2) meilleur que Mahattan pure
mais je ne sais pas trop ce que ça implique    
Et toi donc ?
 
Est-ce qu'on pourais revenir sur le problème de l'optimalité aussi,
tu dis que tu n'a jamais reussi a descendre à 61 coups

ben 61 coups, c'est très (trop) profond pour un arbre d'énumération, à moins d'avoir un très bon algo branch and bound, ce qui n'est pas le cas avec "manhattan distance". Pour l'heuristique, prouve moi en quoi la tienne est admissible ? je ne pense pas qu'elle le soit donc tu ne pourras pas affirmer d'avoir trouvé une solution optimale.

je n'affirme pas, je me demande ; Je n'ai pas encore bien compris A star
Ce que je trouve louche pour l'instant, c'est de sortir de A star à la premiere matrice avec une distance de 0;
Certe, cette matrice est solution, mais correspont-elle au chemin optimale, je ne sais pas,
 
Avec pour heuristique Manhattan*((n+m)/2) je génère mois de matrice qu'avec Manhattan pure, c'est tous ce que je peut te dire
 
je ne comprend pas "en quoi" le calcul de la distance pourait faire dévier la solution optimale  
 
qu'est-ce qu'un algo branch and bound ? je vais aussi chercher sur google
 

Ben oui elle est optimale ... tu as trouvé la solution en 0 mouvements (le plateau de départ est le plateau d'arrivé). Certes, tu génères moins de matrices mais ta solution n'est plus assurée d'être optimale   car tu peux surestimer le coût "nombre de mouvement qui reste à faire pour aller au plateau solution". Utilise Manhattan pur , c'est la meilleure heuristique admissible connue pour ce jeu, cherche pas plus loin .

Et bien non, pour la moment je prefere Manhattan*((N+M)/2)
 
pour la matrice suivante
 
 1|12|10| 4
 2|  0|15| 3
 5|14| 8| 7
13| 9| 6|11
 
Le nombre de matrice générées est 20350
Le temps de resolution est de 3 minutes
Le nombre de mouvements à effectuer pour ranger cette matrice est 45
 
Avec Manhattan pure, et bien j'en suis 240_000 matrices générées
Le programme mouline dans le vide, il ne trouve pas de solution depuis 45 minutes
 
Peut-etre est-ce une question d'ordre dans ma liste Open

Non parce que tu auras trop de matrice générées . Les matrices 4*4 c'est rare de pouvoir les résoudre. Et si tu ne veux pas d'une solution optimale, alors ta solution n'a pas d'interet .

 
j'ai pas compris ce que tu veux dire ? peut-tu reformuler s'il te plais
 
Edit :: finalement, je viens de m'apercevoire que j'ai fait des erreurs dans mon implémentation, et que ça marche pas du tout comme je le pensais
           mes resultats son donc completement faussés.

laisse bet, ... alors tu as débuggé ? présente moi un résultat à titre de comparaison avec les miens

Pour le cas N°1 que tu as donné en debut de topic,
j'obtiens 58 deplacement et 131517 matrice générées
contre 44 et 19192 selon toi
 
J'aimerai bien savoir en quoi different nos methodes

effectivement, c'est pas une solution optimale ça, et tu mets combien de temps à trouver ?

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