[jeu]problème de performance d'un algo

Bonjour !

Je suis en train de faire "l'ia" d'un jeu. J'ai dans mon alphabeta un problème de vitesse. Dès une profondeur de 3 demi coups il met 300 ans...
En analysant les temps mis par chaque fonction, j'ai pu voir que cela venait de mes fonctions "jouerCoup" et "defaireCoup". Effectivement ces fonctions posent problème.
Je m'explique. Le jeu, nommé dvonn, a un systeme de connexion. Il y a trois pièces nommées "dvonn". Toutes les autres pièces du plateau doivent être reliées (directement ou indirectement par une autre pièce) au dvonn, sinon elles sont éliminées du plateau. Donc, à chaque coup joué, je dois vérifier si des pièces ne se retrouvent pas isolées. Hors ici la seule solution que j'ai trouvée n'est pas performante du tout. Je pars de chaque case ou se situe un dvonn puis pour chaque case je fais cette fonction récursive :
(caseTraitees est une List à laquelle sont ajoutées les case traitées)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

private void traiterCase(Case c, Plateau p){ List liste = getListCaseAutour(c, p);//donne la liste des cases qui sont autour Iterator iter = liste.iterator(); while (iter.hasNext()) {//pour chaque case de la liste Case element = (Case) iter.next(); if(!casesTraitees.indexOf(element ) != -1){//si la case n'a pas encore été traitée on continue element.setEtat(CONNECTE); casesTraitees.add(element); traiterCase(element, p); } } }

---

merci pour vos idées :)
n'hésitez pas à me demander des précisions si je me suis mal expliqué !
daoud

Utilise des pointeurs.Au lieu de passer tout le plateau à ta fonction,passe lui juste l'adresse du plateau,idem pour l'élément.Il peut aussi y avoir une pile énorme si ta fonction est appélée trés souvent,ça peut ralentir le tout énormément.

Salut,

j'utilise Java, donc tout est transmis par référence.

pour illustrer mon propos voici 3 images :

http://davidfranck.chez.tiscali.fr/dvonn.jpg

a+
daoud

Bonjour,

les algorithmes récursifs peuvent être très bons sur le papier, mais se révéler très mauvais à l'implémentation en fonction des langages. En effet, si celui-ci a une gestion de la mémoire qui n'est pas spécialement prévue pour le récursif, tu te retrouves en gros à réalloueur tout à chaque fois, et donc ensuite à devoir tout désallouer?

Ceci dit, je ne sais pas comment Java traite le récursif, mais j'ai comme un doute sur ses performances dessus.

Essaye par exemple de coder un algorithme itératif naïf (parcours de toutes les cases ou un truc du genre), et regarde ce que ca donne du point de vue des performances.

Merci,

Mais, je me demande s'il n'y a pas un autre algo qui me permettrait de déterminer si une pièce est reliée...
Je vais essayer en itératif, mais l'eventuelle amélioration ne sera pas à mon avis suffisante.

a+
daoud

c'est un problème de graphe, tu devrais peut etre chercher de ce coté !

Merci pour ta réponse,

peux-tu me donner deux trois mots-clé en plus pour que j'affine mes recherches ? Merci :)

daoud

a mon avis tu devrais essayer de trouver un algo permettant de vérifier qu'un graphe est connexe, c'est à dire qu'il existe un chemin entre 2 sommets quelconques.
Si ton graphe n'est pas connexe, ça signifie que tu as trouvé au moins un sommet non relié au reste du graphe.
tu recherches le sous-graphe connexe contenant ce sommet et voilà

Merci hamster, c'est clairement la piste qu'il me fallait :)

a+
daoud

de rien, bonne continuation dans ton projet

Me revoilà,

je me permets d'enlever la mention résolu afin de poser une nouvelle question :
Comment détecter si il y a une possibilité de cassure, ce qui m'éviterai de faire la gestion de connexion, car le temps de calcul de la fonction joueCoup est de 20004ms en profondeur 4 dont 19924 pour la gestion des connexions. Il faudrait donc un système qui me permette de déterminer s'il y a une possiblité de cassure...
Je suis dessus depuis hier et rien ne vient. Une idée ?

merci :)
daoud

ps : j'ai déjà gagné du temps avec l'algorithme BFS de parcours de graph, merci hamster ;)

Le trésor était sous le fourneau....
Il suffisait que je vérifie des conditions comme :
- le graphe composé des case connexes à la case départ doit être connexe
- le pile déplacée ne doit pas contenir de dvonn...

merci hamster, c'est toujours grâce à ta piste :)

daoud

j'y suis pas pour grand chose !!

Mais c'est quand même dans ce genre de problèmes qu'on voit tout l'intéret de l'algorithmie. La connaissance ultra poussée d'un langage, apprise en cours ou en autodidacte, ne suffit pas