Discussion :

[Yachas]

Bonjour,
je me suis lancé dans la construction d'un arbre n-aire avec tout un tas de fonction qui ajoute un noeud, en supprime etc... Enfin que du déjà vu pour beaucoup d'entre vous !! Moi, je découvre et j'apprends et je dois dire que je galère ^^.

J'ai deux questions :

Dans une vie antérieure, j'avais fait la découverte d'un algorithme ou d'un code qui permettait de modeliser un arbre à partir d'une liste de caractère ou d'un tableau... Je n'arrive plus à mettre la main dessus, est ce que quelqu'un aurait un petit bout de quelque chose pour me rendre moins bête ?

l'autre question, ben... Comment je peux faire pour sauvegarder mon arbre et le stocker dans un fichier sans être obliger de relancer toute la procédure de reconstruction de mon arbre ?

Bon, je sais pas si j'ai été trop clair
En tout cas, merci pour vos réponses.
A+

[aepli]

Bonsoir,

Pour ta question concernant l'enregistrement de ton arbre, tu peux peut être regarder du côté de la sérialisation de tes données: Pickle.

Par contre désolé pour l'algo, je me suis arrêté aux arbres binaire

Salutations.

[tyrtamos]

Bonjour,

Tu peux créer un arbre sous forme de liste (ou plutôt une liste de liste de liste...), en disposant ainsi de toutes les fonctions de manipulation de listes qui sont puissantes chez Python. De plus une liste python peut contenir n'importe quel objet, y compris des objets complexes créés à partir d'une classe.

Pour ce qui concerne le stockage sur disque, j'utilise shelve (http://docs.python.org/library/shelve.html). Tu peut t'inspirer de mon petit tuto (http://python.jpvweb.com/mesrecettes...e_recup_objets). Il faudra vérifier qu'il stocke bien les objets créés sous forme de classe, mais en ce qui concerne les objets python de base, ça marche très bien.

Tyrtamos

[pacificator]

Bonjour,

Perso, pour sauvegarder les arbres, je tue des castors


mais pour créer, modifier et sauvegarder des données sous forme d'arbre, le format XML me paraît le plus adapté et le module elementTree devrait répondre à ton besoin.

[rambc]

Perso, pour sauvegarder les arbres, je tue des castors

Barbare !

[rambc]

Pour ce qui concerne le stockage sur disque, j'utilise shelve ...

Vois-tu un avantage à utiliser shelve au lieu de pickle ?

[tyrtamos]

En fait, je n'utilise que shelve et je ne connais pas pickle. Quand il m'a fallu choisir la 1ère fois, j'ai trouvé shelve très simple à utiliser: ça marche comme un dictionnaire. On peut d'ailleurs simuler facilement ce comportement avec une classe dérivée de dict.

Tyrtamos

[Yachas]

Bonjour à tous et merci pour vos réponses...

Bref, j'ai du grain à moudre ^^

J'aime bien la solution Shelve, elle me semble plus facile à mettre en oeuvre (enfin pour moi et mon petit niveau). Par contre, le coté "créer un arbre sous forme de liste (ou plutôt une liste de liste de liste...), en disposant ainsi de toutes les fonctions de manipulation de listes" reste en core un mystère pour moi
si tu as un bout de code pour me montrer, je suis preneur.

Faut que je regarde également la solution " format XML " que je ne connais pas mais pour le peu que j'en ai vu sur le lien que tu m'as fourni, cela semble prometteur.

Concernant "sérialisation de tes données: Pickle", je ne sais pas ... Faut que j'approfondisse... Mais quelle est l'avantage réel entre Pickle et Shelve... Y a t'il plus d'avantage à utiliser l'un ou l'autre ?

Pffff que de solutions proposées et pour lesquelles je ne connais rien. Que le chemin est long et sinueux

[fred1599]

Concernant "sérialisation de tes données: Pickle", je ne sais pas ... Faut que j'approfondisse... Mais quelle est l'avantage réel entre Pickle et Shelve... Y a t'il plus d'avantage à utiliser l'un ou l'autre ?

Tu veux dire cpickle, car pickle n'est plus trop utilisé, car beaucoup moins performant niveau rapidité.

Le module shelve est basé sur cpickle pour fournir un système de dictionnaire persistent.

Un exemple de code avec cPickle

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
from cPickle import loads, dumps
class MyClass(object):
    def __init__(self):
        self.data=[1, 2, 3]

instance_of=MyClass()
instance_of.data.append(56)
serialisation=dumps(instance_of)
serialisation
"ccopy_reg\n_reconstructor\np1\n(c__main__\nMyClass\np2\nc__builtin__\nobject\np3\nNtRp4\n(dp5\nS'data'\np6\n(lp7\nI1\naI2\naI3\naI56\nasb."
more=loads(serialisation)
more.data
[1, 2, 3, 56]

[rambc]

Dans une vie antérieure, j'avais fait la découverte d'un algorithme ou d'un code qui permettait de modeliser un arbre à partir d'une liste de caractère ou d'un tableau... Je n'arrive plus à mettre la main dessus, est ce que quelqu'un aurait un petit bout de quelque chose pour me rendre moins bête ?

Proposes un exemple visuel d'arbre et on pourra te proposer une solution.

[dahtah]

Je ne réponds pas à la question que tu poses, mais pour la gestion des arbres tu peux utiliser le design pattern composite qui est fait pour ça.
Après, c'est peut-être tuer une mouche avec un bazooka si c'est un cas simple.
Il simplifierai la sauvegarde de ton arbre en appelant de manière récursive une méthode de sauvegarde de chaque feuille, sans te soucier de la profondeur de l'arbre.
Bon courage

[tyrtamos]

Bonjour,

Par contre, le coté "créer un arbre sous forme de liste (ou plutôt une liste de liste de liste...), en disposant ainsi de toutes les fonctions de manipulation de listes" reste en core un mystère pour moi
si tu as un bout de code pour me montrer, je suis preneur.

Voilà quelques éléments improvisés pour te montrer quelques aspects des listes et des arbres:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
# liste composée de 5 nb entiers (len(a)=5):
a = [1, 2, 3, 4, 5]
 
# on ajoute 6 à la liste:
a.append(6)  # => la nouvelle liste est: [1, 2, 3, 4, 5, 6]
 
# on retire le 6:
x = a.pop(-1)  # => la nouvelle liste est: [1, 2, 3, 4, 5] et x=6 
 
# NB: les 2 méthodes append et pop permettent d'utiliser la liste comme une pile
 
# on retire le 3 qui correspond à l'index 2:
x = a.pop(2)  # => la nouvelle liste est: [1, 2, 4, 5] et x=3
 
# on le réinserre
a.insert(x, 2)  # => la nouvelle liste est: [1, 2, 3, 4, 5]
 
# liste hétérogène:
a = [1, "toto", 12, 3.14159, complex(4, 5)]
 
# on ajoute une instance de l'objet Data à la fin:
class Data(object):
    def __init__(self, nom, couleur="", hauteur=0):
        self.nom = nom
        self.couleur = couleur
        self.hauteur = hauteur
a.append(Data("toto"))
# l'instance de la classe Data ayant pour nom "toto" est désormais à la fin de a. 
# D'ailleurs, rien n'empêche d'avoir une liste composée uniquement d'instances d'objets déclarés comme class.
# On peut afficher son nom avec:
a[-1].nom  # affiche: toto
 
# voilà un arbre:
a = [5, 6, [1], [6, [8, 4], 7, [12, [48]], 0], 77]
# ce qui veut dire que:
# l'élément d'indice 2: [1] est une liste
# l'élément d'indice 3: [6, [8, 4], 7, [12, [48]], 0] est une liste qui contient des listes
# etc...
 
# parcours récursif de l'arbre: exemple d'une fonction d'affichage
def affiche(a):
    if isinstance(a, list):
        ch = '['
        if len(a)!=0:
            for x in a:
                ch += "%s, " % affiche(x)
            ch = ch[:-2]  # pour retirer le dernier ', ' en trop
        ch += ']'
    else:
        ch = "%s" % a
    return ch
 
print a
# affiche: [5, 6, [1], [6, [8, 4], 7, [12, [48]], 0], 77]
 
print affiche(a)
# affiche: [5, 6, [1], [6, [8, 4], 7, [12, [48]], 0], 77]
 
# accès à l'élément de valeur 8:
print a[3][1][0]
 
# d'autres fonctions et méthodes applicables à la manipulation des listes:
b = a[1:3]  # ne retient dans b que les indices 1 et 2 de la liste a
 
a.extend(b) # ajoute en fin de liste la liste c
print a  # affiche [5, 6, [1], [6, [8, 4], 7, [12, [48]], 0], 77, 6, [1]]
 
# il y a aussi: recherche, tri, comptage, ...

Au delà de ça: regarde dans les docs de formation du site, il y a de très bonnes choses.

Tyrtamos

[Yachas]

Bonjour,
Bon... Après un peu de recherche, j'ai compris que Shelve était nettement plus interressant que CPickle. à priori, Cpickle pratique la sérialisation mais n'a pas de système de stockage persistant. alors que Shelve offre une solution un peu plus complète car il sérialise et stocke... Bon, je vous laisse juge si j'ai compris ou pas

Après, c'est peut-être tuer une mouche avec un bazooka si c'est un cas simple.

Ne flatte pas mon coté poète... La flaterie ne te menera nulle part ^^
l'idée est de stocker un arbre n-eme de grande taille... Genre le nombre de position jouable dans un wargame

mais pour la gestion des arbres tu peux utiliser le design pattern composite qui est fait pour ça.

Sapristi, mais qu'est ce que c'est que ce truc ?

Proposes un exemple visuel d'arbre et on pourra te proposer une solution.

Par exemple, cela devrait ressembler à un truc comme ça en beaucoup plus grand

Voilà voilà...
Merci pour vos commentaires
A+

[rambc]

Voici un exemple simple d'arbre que j'ai fait pour manipuler une table des matières :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#!/usr/bin/env python
#coding=utf-8
 
import copy
 
class tableOfContent(object):
    """
    This class is used to build a table of content from the start to the end.
    You can't act on a precedent title build.
    theCurrentLevel in N and zero is for the title of a document
    """
    def __init__(self, theFirstTitle, theTitleLevel, isTheTitleNumbered = True):
        if not isinstance(theFirstTitle, str):
            raise ValueError, "WARNING : '' theFirstTitle '' must be the string of the title."
 
        if not isinstance(theTitleLevel, int):
            raise ValueError, "WARNING : '' theTitleLevel '' must be an integer."
 
        if theTitleLevel < 0:
            raise ValueError, "WARNING : '' theTitleLevel '' must be a positive integer."
 
        self.titles = [ { 'text': theFirstTitle,
                          'content': None,
                          'numbered': bool(isTheTitleNumbered),
                          'internalComment': None } ] # To indicate for example that a title comes from an imported file.
        self.level = theTitleLevel
 
        self.__missingTitle = '¨missingTitle'
 
    def append(self, newTitleOfSameLevel, isTheTitleNumbered = True):
        """
        To add a new title of the same lavel.
        """
        if isinstance(newTitleOfSameLevel, str):
            self.titles.append( { 'text': newTitleOfSameLevel,
                                  'content' :None,
                                  'numbered':bool(isTheTitleNumbered),
                                  'internalComment': None } )
        else:
            raise ValueError, "WARNING : you can only append the string of a title."
 
    def addSubTitle(self, subTitle, levelOfTheSubTitle, isTheTitleNumbered = True):
        """
        To add a new title of the same lavel.
        """
        if not isinstance(subTitle, str):
            raise ValueError, "WARNING : a title must be the string of the title."
 
        if not isinstance(levelOfTheSubTitle, int):
            raise ValueError, "WARNING : a level of a title must be an integer."
 
        if levelOfTheSubTitle < 0:
            raise ValueError, "WARNING : a level of a title be a positive integer."
 
        if levelOfTheSubTitle <= self.level:
            raise ValueError, "WARNING : use Python's addition on tableOfContent() classes to add a title with lower level than the current one."
 
        contentToAddd = tableOfContent(subTitle, levelOfTheSubTitle, isTheTitleNumbered)
 
        if self.titles[-1]['content'] == None:
# We must take care of things like :
#    Titre I
#            Sous Sous Titre I-1-a
            if contentToAddd.level == self.level + 1:
                self.titles[-1]['content'] = contentToAddd
            else:
                contentWithHoles = tableOfContent(self.__missingTitle , self.level + 1, False)
                self.titles[-1]['content'] = contentWithHoles + contentToAddd
        else:
            self.titles[-1]['content'] += contentToAddd
 
    def __add__(self, content):
        if not isinstance(content, tableOfContent):
            raise ValueError, "WARNING : you can only add tableOfContent() to tableOfContent()."
 
        additionOfToc = copy.deepcopy(self)
 
# We have to take care of missing title.
        if additionOfToc.titles[-1]['text'] == self.__missingTitle and len(additionOfToc.titles) <> 1:
            additionOfToc.titles = [ additionOfToc.titles[0] ]
 
# We have the same level of content.
# We have to take care of missing title.
        if content.level == self.level:
            if additionOfToc.titles[0]['text'] == self.__missingTitle and additionOfToc.titles[0]['content'] == None:
                additionOfToc = content
            else:
                additionOfToc.titles += content.titles
 
            return additionOfToc
 
# We have a sub content.
        if content.level > self.level:
            if additionOfToc.titles[-1]['content'] == None:
                contentWithHoles = tableOfContent(self.__missingTitle , self.level + 1, False)
                additionOfToc.titles[-1]['content'] = contentWithHoles + content
            else:
                additionOfToc.titles[-1]['content'] += content
            return additionOfToc
 
# We have an "up" content. We must take car of the maximum level of self.content
# because we can have something like (that we accpet) :
#        Sous Sous Titre I-3-a
#        Sous Sous Titre I-3-b
#        Sous Sous Titre I-3-c
#    Titre II
#        Sous Titre II-1
#        Sous Titre II-2
        contentWithHoles = tableOfContent(self.__missingTitle , self.level - 1, False)
        additionOfToc = contentWithHoles + additionOfToc
        return additionOfToc + content
 
    def isValid(self):
        for i  in range(len(self.titles)):
            if self.titles[i]['text'] == self.__missingTitle:
                return False
 
# Are the contents valid ?
        for i  in range(len(self.titles)):
            if self.titles[i]['content'] <> None:
                if not self.titles[i]['content'].isValid():
                    return False
 
        return True
 
    def __str__(self):
        """
        Visual ASCII tree
        """
        asciiTree = ''
        titleNumber = 0
 
        for i in range(len(self.titles)):
            asciiTree += "    "*self.level
 
            if self.titles[i]['numbered']:
                titleNumber += 1
                asciiTree += str(titleNumber) + ') '
 
            asciiTree += self.titles[i]['text']
 
            if self.titles[i]['internalComment']:
                titleNumber += 1
                asciiTree += '  << ' + str(self.titles[i]['internalComment']) + ' >>'
 
            asciiTree += '\n'
 
            if self.titles[i]['content'] <> None:
                asciiTree += str(self.titles[i]['content'])+'\n'
 
        return asciiTree[:-1]
 
if __name__ == '__main__':
    from myToc import *
 
    testTOC1 = tableOfContent('Titre I', 1)
    testTOC1.addSubTitle('Sous Titre I-1', 2)
    testTOC1.addSubTitle('Sous-sous Titre I-2-a', 3)
    testTOC1.addSubTitle('Sous-sous Titre I-2-b', 3)
    testTOC1.addSubTitle('Sous Titre I-3', 2)
 
    testTOC2 = tableOfContent('Titre II', 1)
    testTOC2.addSubTitle('Sous Titre II-1', 2)
    testTOC2.addSubTitle('Sous Titre II-2', 2)
 
    testTOC1 += testTOC2
    print testTOC1

Je pense que c'est un exemple d'implémentation d'un arbre.

[Antoine_935]

Ceci n'est pas un arbre. C'est un graphe. En cause, l'élément E qui a deux "entrées": les éléments d'un arbres ont un degré d'entrée de 1 ou zero.

[rambc]

Pour les graphes, on peut utiliser une matrice si l'arbre est de taille raisonnable. Voir cette page.

Pour travailler avec des arbres plus grands, le module numpy permet d'utiliser des tableaux très grands.

Tu peux aussi regarder le module NetworkX.

Tout dépend du type d'arbre utilisé.

[Yachas]

Ceci n'est pas un arbre. C'est un graphe. En cause, l'élément E qui a deux "entrées": les éléments d'un arbres ont un degré d'entrée de 1 ou zero.

Ehm... Comme tu peux le constater, mes connaissances en math sont laborieuses... Cela dit, tu as raison et j'avais construit sciement les entrées de l'element E . En effet, je me suis apperçu qu'un pion peut se retrouver à une même position en parcourant un itinéraire différent et finalement proposer une même situation... J'en deduis qu'il me faut aussi orienter mes recherches vers la théorie des graphes ^^.

Pour les graphes, on peut utiliser une matrice si l'arbre est de taille raisonnable. Voir cette page : Incidence_matrix

Bon, je dois aussi me diriger vers les matrices + les graphes + les arbres...
Pfff... Je devrais être prêt aux alentours de l'an 4808
En tout cas merci pour votre aide

[rambc]

J'en deduis qu'il me faut aussi orienter mes recherches vers la théorie des graphes ^^.
Bon, je dois aussi me diriger vers les matrices + les graphes + les arbres...
Pfff... Je devrais être prêt aux alentours de l'an 4808

Si tu t'en tiens juste aux résultats, la théorie des graphes est facile à aborder. Certains résultats sont vus en 1ère et en Term. ES.

Il semblerait que tu souhaites travailler sur un jeu. Lequel ? Que cherches-tu à faire ? Il faut faire attention car avec les jeux même les plus simples il n'est pas aisé de programmer une résolution automatique.

[Yachas]

bonjour,
Damned, suis-je demasqué ?
Oui, je tente de programmer un wargame relativement simple, avec des rêgles trés simples... J'ai déjà bien avancé l'interface graphique avec WxPython ainsi que du respect des rêgles par le programme.

Maintenant, je m'attaque à l'IA du programme...
Mes recherches m'ont ammené vers MOGO, et son algorithme UCT + Monte Carlo dont je dois etre le seul au monde à ne rien connaitre (puisque tout ce que j'ai trouvé, en gros, jusquà présent concerne des gens qui disent que c'est le top mais qui n'expliquent pas comment cela fonctionne réellement) et qui ne mobilisent pas vraiment les gens du forum Algoritme ^^

Je tatonne sans trop savoir où me dirriger pour le moment, y a qu'à voir l'ensemble du post pour comprendre mon ignorence. En plus, je suis loin d'avoir effectué une terminale S
Autant te dire que le challenge est d'envergure

Si tu as des infos sur le sujet je suis preneur.

[dahtah]

Salut,

Sapristi, mais qu'est ce que c'est que ce truc ?

Excuse moi, j'avais mal compris ton problème (graphe binaire). Ma réponse n'était pas adaptée. Le design pattern composite n'a d'intérêt que dans un arbre d'objets en POO. Il permet de gérer la hiérarchie entre ceux-ci de manière propre.

Concernant la méthode de Monte-Carlo il en existe plusieurs. Sur internet, il est difficile d'en trouver une bonne explication, car peu de gens la connaisse vraiment (la théorie est assez ardue). Les deux sous-méthodes de Monte-Carlo où je peux t'éclairer sont :
* l'approximation de la valeur d'une intégrale de dimension n
* le rejeu de modèle physique pour estimer une variation future
Malheureusement, je ne sais pas qu'elle méthode de Monte-Carlo est utilisé en IA.
Bon courage avec ton graphe, ne reste plus qu'à mettre en place les solutions proposées ...