Discussion :

[zais_ethael]

Salut à tous.
Bon, je sais, le sujet a déja été traité quelques fois mais j'ai beau faire des recherches dans ce forum je ne trouve pas de réponse interressante, alors je le relance au cas ou.
Je cherche une classe pour les arbres n-aire pour implémenter un algorithme de type minimax dans un jeu de société (un othello).
La stl ne contient rien à ce sujet (j'ai déja vu citées les maps mais ca n'a rien à voir). Quand à boost il ne contient qu'une classe pour les graphs. Mais même si un graph peut normalement être utilisé comme un arbre, je ne suis pas sur que ce soit très pratique (qu'on me dise si je me trompe - je n'ai pas essayé).
Sinon, si quelqu'un a une autre proposition je suis preneur.
Merci d'avance.

[Médinoc]

Au pire, tu peux toujours te faire une structure Noeud qui comprend une liste de fils ou de pointeurs sur fils...

[zais_ethael]

Bien sur, la solution du "je le fais moi même" est envisageable dans ce cas ci, mais c'est sans compter que je suis très fainéant .
Et puis si jamais ca existe, c'est quand même mieux d'avoir un truc bien fait, bien pensé, et tant qu'on y est "stl-like" si possible.

[loufoque]

boost graph contient déjà l'algorithme minimax.
Il y a aussi un projet pour les arbres dans boost, développé lors du Google SoC.

[zais_ethael]

Tu aurais pas le lien vers ce truc la s'il te plait? J'ai beau rechercher sur google je ne vois aucune page relative à un travail effectué sur ce projet.

[Jean-Marc.Bourguet]

Ça ne réponds peut-être pas à ta question, mais quand j'ai implémenté le minimax, je n'ai jamais eu besoin de contruire l'arbre explicitement.

[zais_ethael]

J'ai un peu de mal à comprendre le principe avec ses subtilités, alors j'aimerais bien commencer par implémenter sa définition la plus stricte (parcours d'un arbre donc) pour ensuite passer à l'une ou l'autre personnalisation/optimisation.

[loufoque]

http://www.unet.univie.ac.at/~a00573...2006/doc/html/

[zais_ethael]

Ok, merci.
Je vais jeter un coup d'oeil à ca et à boost graph aussi.

[koala01]

Salut,

Une des solutions "facile" est simplement la création d'une classe Noeud du genre de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
class Noeud
{
    private:    
        std::list<Noeud> Enfants; //les noeuds enfants
        Noeud* Parent;   //la possiblité de récupérer le noeud parent
        //les autres membres qui t'intéressent
    public:
        //les méhtodes qui t'intéressent
}

Evidemment, selon le type d'acces dont tu as besoin (aléatoire ou non, indexé ou non, unique ou non...) tu peux très bien décider d'utiliser un autre conteneur