Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
8444 connectés 

 


 Mot :   Pseudo :  
 
 Page :   1  2  3  4  5  6  7  8  9  10  11  12  13  14  15
Auteur Sujet :

[Ada][Topic Unic][Open Source] Je fais péter mes codes.

n°2546375
Profil sup​primé
Posté le 31-05-2006 à 12:03:26  answer
 

Reprise du message précédent :

Giz a écrit :

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


 
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


Message édité par Profil supprimé le 31-05-2006 à 12:10:23
mood
Publicité
Posté le 31-05-2006 à 12:03:26  profilanswer
 

n°2546376
Giz
Posté le 31-05-2006 à 12:05:25  profilanswer
 

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

n°2546377
Profil sup​primé
Posté le 31-05-2006 à 12:58:42  answer
 

Giz a écrit :

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 !  [:kernel-panic]

n°2546378
Giz
Posté le 31-05-2006 à 13:43:34  profilanswer
 

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

n°2546379
Profil sup​primé
Posté le 31-05-2006 à 14:28:36  answer
 

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  :pt1cable:  
et 2 : il me manque un ou deux elements dans ma liste solution  :??:  
 
par hasard, tu n'aurais pas des symptomes similaire ?

n°2546380
Giz
Posté le 31-05-2006 à 14:46:20  profilanswer
 

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.

n°2546381
Profil sup​primé
Posté le 31-05-2006 à 15:47:00  answer
 

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.  [:cid]  
 
Pour ce qui est du dernier élément, ça y est, je l'ai trouvé  :lol:  
 
Si tu veux d'autres matrices, plus ou moins melangées ....
 
 

n°2546382
Profil sup​primé
Posté le 01-06-2006 à 12:24:51  answer
 

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

n°2546383
Giz
Posté le 01-06-2006 à 12:29:19  profilanswer
 

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.

n°2546384
Profil sup​primé
Posté le 01-06-2006 à 12:47:56  answer
 

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
 

mood
Publicité
Posté le 01-06-2006 à 12:47:56  profilanswer
 

n°2546385
Giz
Posté le 01-06-2006 à 16:43:55  profilanswer
 

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


Message édité par Giz le 01-06-2006 à 16:44:21
n°2546386
Profil sup​primé
Posté le 01-06-2006 à 17:42:13  answer
 

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

n°2546387
Giz
Posté le 01-06-2006 à 18:12:25  profilanswer
 

Non parce que tu auras trop de matrice générées [:itm]. 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 :/.

n°2546388
Profil sup​primé
Posté le 01-06-2006 à 18:20:01  answer
 

Giz a écrit :

Non parce que tu auras trop de matrice générées [:itm]. 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.


Message édité par Profil supprimé le 01-06-2006 à 22:26:49
n°2546389
Giz
Posté le 02-06-2006 à 11:32:57  profilanswer
 

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

n°2546390
Profil sup​primé
Posté le 02-06-2006 à 12:34:54  answer
 

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

n°2546391
Giz
Posté le 02-06-2006 à 13:19:00  profilanswer
 

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

n°2546392
Profil sup​primé
Posté le 02-06-2006 à 13:31:41  answer
 

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

n°2546393
Giz
Posté le 02-06-2006 à 15:42:49  profilanswer
 

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

n°2546394
Profil sup​primé
Posté le 02-06-2006 à 20:53:36  answer
 

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

n°2546395
Profil sup​primé
Posté le 02-06-2006 à 22:17:14  answer
 

:sol:  [:666rip666]  :sol:  
 
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  :heink:  
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  :jap:  
 
Mon "Uniform" est le suivant

Code :
  1. Function Uniform(Precedente,Suivante,terminale : T_Matrice) return float is
  2.      Somme : constant Float :=
  3.      Heuristic(suivante,Terminale) -
  4.      Heuristic(precedente,Terminale) + 2.0;
  5.   begin
  6.      Return Somme;
  7.   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  :lol:  
59 deplacements pour ranger la matrice contre 47  :heink:  
un peut moins de 50 minutes contre 10 secondes  :cry:  
 
par contre, je ne sais plus quoi faire pour trouver l'optimal, ni pour diminuer les temps de resolution  :??:


Message édité par Profil supprimé le 02-06-2006 à 23:58:17
n°2546396
Profil sup​primé
Posté le 03-06-2006 à 21:21:55  answer
 

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

n°2546397
Profil sup​primé
Posté le 04-06-2006 à 20:29:14  answer
 

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

n°2546398
Giz
Posté le 05-06-2006 à 09:24:48  profilanswer
 


 
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)

Message cité 1 fois
Message édité par Giz le 05-06-2006 à 09:45:42
n°2546399
Profil sup​primé
Posté le 05-06-2006 à 10:58:15  answer
 

Giz a écrit :

Tu devrais généré au mieux ~50 matrices (moyenne des profondeurs pour une matrice 4*4).


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  :cry:  
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  :p  
 

n°2546400
Giz
Posté le 05-06-2006 à 11:22:18  profilanswer
 


 
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 :/.


Message édité par Giz le 05-06-2006 à 11:23:12
n°2546401
Profil sup​primé
Posté le 05-06-2006 à 11:56:36  answer
 

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

n°2546402
Giz
Posté le 05-06-2006 à 12:20:41  profilanswer
 

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

Message cité 1 fois
Message édité par Giz le 05-06-2006 à 12:21:58
n°2546403
Profil sup​primé
Posté le 05-06-2006 à 12:46:49  answer
 

Giz a écrit :

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

n°2546404
Profil sup​primé
Posté le 05-06-2006 à 13:28:48  answer
 

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

n°2546405
Giz
Posté le 05-06-2006 à 14:43:53  profilanswer
 

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.

n°2546406
Profil sup​primé
Posté le 05-06-2006 à 15:03:02  answer
 

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
 
 

n°2546407
Profil sup​primé
Posté le 05-06-2006 à 15:10:39  answer
 

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

n°2546408
Profil sup​primé
Posté le 05-06-2006 à 15:15:06  answer
 

Merci, merci Giz

n°2546409
Giz
Posté le 05-06-2006 à 15:27:28  profilanswer
 

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

n°2546410
Profil sup​primé
Posté le 05-06-2006 à 16:38:31  answer
 

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

n°2546411
Giz
Posté le 05-06-2006 à 16:47:27  profilanswer
 

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


Message édité par Giz le 05-06-2006 à 16:49:45
n°2546412
Profil sup​primé
Posté le 05-06-2006 à 17:21:41  answer
 

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 ?  :??:  [:dawa_neowen]  

n°2546413
Profil sup​primé
Posté le 05-06-2006 à 17:23:35  answer
 

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

n°2546414
Giz
Posté le 05-06-2006 à 17:48:18  profilanswer
 


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

n°2546415
Profil sup​primé
Posté le 05-06-2006 à 17:56:16  answer
 
mood
Publicité
Posté le   profilanswer
 

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

Aller à :
Ajouter une réponse
 

Sujets relatifs
Probleme robot google ? Ma source internet ? aidez moiInterface ADA avec C
Projet de frontend Open-Source pour émulateursOpen Office: Base de données
code source pdf ?Modifier le code source de SIP-Communicator
[JS] Pb avec un page de javascripts et module open flash chart[ADA] /!\ Combien on peux boire de biere JEUDI MIDI §§§ la defense ??
Fonction window.open (javascript) 
Plus de sujets relatifs à : [Ada][Topic Unic][Open Source] Je fais péter mes codes.


Copyright © 1997-2025 Groupe LDLC (Signaler un contenu illicite / Données personnelles)