IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

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


Sujet :

Algorithmes et structures de données

  1. #1
    Membre habitué Avatar de le Daoud
    Profil pro
    Inscrit en
    Novembre 2002
    Messages
    287
    Détails du profil
    Informations personnelles :
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations forums :
    Inscription : Novembre 2002
    Messages : 287
    Points : 169
    Points
    169
    Par défaut [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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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

  2. #2
    Membre averti
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mai 2002
    Messages
    255
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Mai 2002
    Messages : 255
    Points : 445
    Points
    445
    Par défaut
    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.

  3. #3
    Membre habitué Avatar de le Daoud
    Profil pro
    Inscrit en
    Novembre 2002
    Messages
    287
    Détails du profil
    Informations personnelles :
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations forums :
    Inscription : Novembre 2002
    Messages : 287
    Points : 169
    Points
    169
    Par défaut
    Salut,

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

    pour illustrer mon propos voici 3 images :



    a+
    daoud

  4. #4
    Modérateur
    Avatar de gangsoleil
    Homme Profil pro
    Manager / Cyber Sécurité
    Inscrit en
    Mai 2004
    Messages
    10 148
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Savoie (Rhône Alpes)

    Informations professionnelles :
    Activité : Manager / Cyber Sécurité

    Informations forums :
    Inscription : Mai 2004
    Messages : 10 148
    Points : 28 113
    Points
    28 113
    Par défaut
    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.
    "La route est longue, mais le chemin est libre" -- https://framasoft.org/
    Les règles du forum

  5. #5
    Membre habitué Avatar de le Daoud
    Profil pro
    Inscrit en
    Novembre 2002
    Messages
    287
    Détails du profil
    Informations personnelles :
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations forums :
    Inscription : Novembre 2002
    Messages : 287
    Points : 169
    Points
    169
    Par défaut
    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

  6. #6
    Membre régulier Avatar de hamster
    Profil pro
    Inscrit en
    Octobre 2003
    Messages
    137
    Détails du profil
    Informations personnelles :
    Âge : 40
    Localisation : France, Rhône (Rhône Alpes)

    Informations forums :
    Inscription : Octobre 2003
    Messages : 137
    Points : 123
    Points
    123
    Par défaut
    c'est un problème de graphe, tu devrais peut etre chercher de ce coté !

  7. #7
    Membre habitué Avatar de le Daoud
    Profil pro
    Inscrit en
    Novembre 2002
    Messages
    287
    Détails du profil
    Informations personnelles :
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations forums :
    Inscription : Novembre 2002
    Messages : 287
    Points : 169
    Points
    169
    Par défaut
    Merci pour ta réponse,

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

    daoud

  8. #8
    Membre régulier Avatar de hamster
    Profil pro
    Inscrit en
    Octobre 2003
    Messages
    137
    Détails du profil
    Informations personnelles :
    Âge : 40
    Localisation : France, Rhône (Rhône Alpes)

    Informations forums :
    Inscription : Octobre 2003
    Messages : 137
    Points : 123
    Points
    123
    Par défaut
    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à

  9. #9
    Membre habitué Avatar de le Daoud
    Profil pro
    Inscrit en
    Novembre 2002
    Messages
    287
    Détails du profil
    Informations personnelles :
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations forums :
    Inscription : Novembre 2002
    Messages : 287
    Points : 169
    Points
    169
    Par défaut
    Merci hamster, c'est clairement la piste qu'il me fallait

    a+
    daoud

  10. #10
    Membre régulier Avatar de hamster
    Profil pro
    Inscrit en
    Octobre 2003
    Messages
    137
    Détails du profil
    Informations personnelles :
    Âge : 40
    Localisation : France, Rhône (Rhône Alpes)

    Informations forums :
    Inscription : Octobre 2003
    Messages : 137
    Points : 123
    Points
    123
    Par défaut
    de rien, bonne continuation dans ton projet

  11. #11
    Membre habitué Avatar de le Daoud
    Profil pro
    Inscrit en
    Novembre 2002
    Messages
    287
    Détails du profil
    Informations personnelles :
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations forums :
    Inscription : Novembre 2002
    Messages : 287
    Points : 169
    Points
    169
    Par défaut
    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

  12. #12
    Membre habitué Avatar de le Daoud
    Profil pro
    Inscrit en
    Novembre 2002
    Messages
    287
    Détails du profil
    Informations personnelles :
    Localisation : France, Loire Atlantique (Pays de la Loire)

    Informations forums :
    Inscription : Novembre 2002
    Messages : 287
    Points : 169
    Points
    169
    Par défaut
    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

  13. #13
    Membre régulier Avatar de hamster
    Profil pro
    Inscrit en
    Octobre 2003
    Messages
    137
    Détails du profil
    Informations personnelles :
    Âge : 40
    Localisation : France, Rhône (Rhône Alpes)

    Informations forums :
    Inscription : Octobre 2003
    Messages : 137
    Points : 123
    Points
    123
    Par défaut
    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

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Probléme de performance.
    Par kikoj dans le forum MS SQL Server
    Réponses: 8
    Dernier message: 10/08/2005, 14h12
  2. Problème de performance avec LEFT OUTER JOIN
    Par jgfa9 dans le forum Requêtes
    Réponses: 6
    Dernier message: 17/07/2005, 14h17
  3. [C#] Probléme de performance avec IsDbNull
    Par jab dans le forum Windows Forms
    Réponses: 8
    Dernier message: 04/04/2005, 12h39
  4. [oracle 9i][Workbench]Problème de performance
    Par nuke_y dans le forum Oracle
    Réponses: 6
    Dernier message: 03/02/2005, 18h38
  5. [ POSTGRESQL ] Problème de performance
    Par Djouls64 dans le forum PostgreSQL
    Réponses: 6
    Dernier message: 26/05/2003, 17h18

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo