biblio d'arbre n-aire

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.

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

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

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.

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.

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

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.

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

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

Salut,

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

Code:

---

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

adobe::forrest ?
Sinon, j'ai un peu la même vision que Jean-Marc : sortir un arbre ne me semble pas apporter grand chose au min-max. C'est de la pure recherche récursive.

Ca dépend comment on le concoit, on peu très bien choisir de conserver un certain nombre de résultats en mémoire pour ne pas avoir à les regénérer.
Bon, ca c'est pour l'exemple, il est vrai que je n'ai pas trop envie de faire de l'optimisation à outrance, mais je voulais quand même explorer cette possibilité.

Je ne suis pas persuadé que cela va t'aider à optimiser.
Si tu veux optimiser le min-max, pars p.ex. sur l'élagage alpha-beta.

Après, si tu veux mémoriser les "noeuds" que tu as explorés, je ne sais pas si garder ton arbre soit très utile. Dans tous les cas, ce sont les feuilles qui nous interessent, ce sont elles qui donneront des valeurs min/max aux divers noeuds. A chaque coup, il faudra redescendre d'un coup, et probablement ré-explorer et évaluer à partir des nouvelles feuilles. A voir. Mais commences plutôt par l'élagage alpha-beta.

Déja fait :D, c'est très efficace d'ailleurs.
Ce que tu dis est vrai mais c'est en admettant que la création des solutions ne soit pas très longue. Dans un jeu de dames par exemple ca irait encore mais dans un othello ca peut être plus long (potentiellement beaucoup de pièces à parcourir et à modifier pour le placement d'une seule nouvelle pièce).
Bien que je n'en sois pas certain, je pense que dans ce cas ce serait plus optimisé de conserver les solutions précédentes. En tous cas je ne peux pas savoir sans avoir essayé.