J'ai une liste d'événements ['one', 'two', 'three']. Ces événements peuvent réussir ou échouer. Je veux construire un arbre de décision pour enregistrer les résultats possibles, c'est-à-dire :

                    <root>
                      /\
      <one_pass>              <one_fail>
          /\                      /\
<two_pass>  <two_fail>  <two_pass>  <two_fail>
...

De plusieurs super answers, je peux voir que la récursivité est la voie à suivre, apparemment en conjonction avec un arbre binaire. Ce avec quoi je me bats, c'est la boucle pour construire la réussite/l'échec à chaque niveau... Est-ce une boucle for ou dois-je utiliser la récursivité ?

Mon point de départ pour le code provient de la réponse que j'ai trouvée ici, copiée ci-dessous pour une référence facile. (Je souhaiterai stocker des valeurs dans chacun des nœuds à un stade ultérieur, puis calculer la somme de celles-ci, j'ai donc commencé ici):

class Node:
    def __init__(self, data, children=None):
        if children is None:
            children = []
        self.data = data
        self.children = children

    def __str__(self):
        return str(self.data)

    __repr__ = __str__

def get_all_paths(node, path=None):
    paths = []
    if path is None:
        path = []
    path.append(node)
    if node.children:
        for child in node.children:
            paths.extend(get_all_paths(child, path[:]))
    else:
            paths.append(path)
    return paths

J'ai construit manuellement ce qui suit pour commencer à travailler sur la façon de créer la structure complète, c'est là que je suis bloqué.

tree = Node("start", [
        Node("one_pass", [
            Node("two_pass"), 
            Node("two_fail")
        ]),
        Node("one_fail", [
            Node("two_pass"),
            Node("two_fail")
        ])
    ])

Après avoir essayé cela, je suis bloqué au niveau de la boucle for .. ce qui me fait penser que je ne suis pas au courant de l'approche à utiliser ici. Si la boucle a créé deux nœuds à chaque passage - créant essentiellement les nœuds enfants gauche et droit en une seule itération - comment puis-je les lier au nœud précédent ? Ai-je besoin d'une méthode qui fait quelque chose comme le pseudo-code suivant ?

for event in events:
    insert_node(my_tree, event, "pass")
    insert_node(my_tree, event, "fail")

NB J'ai 15 niveaux de l'arbre si cela a un impact sur quoi que ce soit.

0
Blue Otter Hat 14 mars 2019 à 19:53

2 réponses

Meilleure réponse

Vous pouvez générer votre arbre en utilisant le code suivant (non récursif) :

def generate_nodes(parent, data):  # adds data_pass and data_fail child nodes to parent
    passed = Node(data + '_pass')
    failed = Node(data + '_fail')
    parent.children.append(passed)
    parent.children.append(failed)

    return [passed, failed]  # returns new nodes


events = ['one', 'two', 'three']
root = Node('root')  # root of our tree
current_level_events = [root]  # nodes of currently processed level

for data in events:  # go through all events
    tmp = []
    for event in current_level_events:
        tmp += generate_nodes(event, data)  # generate events 
    current_level_events = tmp

Implémentation récursive:

events = ['one', 'two', 'three']

def generate_nodes(parent, index):
    if index >= len(events):  # we finished tree generation, no more events found
        return
    data = events[index]
    passed = Node(data + '_pass')
    failed = Node(data + '_fail')
    parent.children.append(passed)
    parent.children.append(failed)
    # generate children for passed and failed nodes
    generate_nodes(passed, index + 1)
    generate_nodes(failed, index + 1)


events = ['one', 'two', 'three']
root = Node('root')  # root of our tree

generate_nodes(root, 0)  # starts tree generation
0
ingvar 14 mars 2019 à 17:20

L'une des raisons pour lesquelles les structures binaires sont si utiles est qu'elles sont très faciles à stocker en mémoire et à indexer avec juste quelques astuces mathématiques.

Si toutes vos conditions sont connues à l'avance, il est très facile de considérer votre liste de ['pass', 'fail', 'pass', 'fail' etc..] comme un nombre binaire ([1, 0, 1, 0]: 10) avec lequel utiliser comme index dans une liste pré-allouée au longueur du total des résultats possibles (2N où N est le nombre de conditions).

Si vous devez stocker des valeurs à chaque étape de la prise de décision (c'est-à-dire stocker une valeur pour ['pass','fail'] ainsi que ['pass', 'fail', 'fail']), c'est un peu plus compliqué, mais toujours pas si difficile. Nous savons qu'un nombre donné de conditions donne 2N résultats possibles, donc nous pouvons également savoir combien de résultats sont donnés avec N-1 conditions, et N-2 etc. Au total, il y a 2N-1 conditions de toutes les listes de conditions plus courtes avant les 2N conditions qui se rapportent à N conditions. En ajoutant notre nombre binaire tel que nous l'avons trouvé précédemment à 2N-1, nous pouvons obtenir un index unique pour chaque liste possible de conditions.

Si vous avez de longues listes de conditions, il est assez facile de voir que la liste des résultats possibles augmente de façon exponentielle. Si vous ne prévoyez jamais de visiter tous les résultats possibles, il peut être avantageux d'utiliser un dictionnaire avec des touches numériques plutôt qu'une liste pour stocker tous les résultats possibles.

Vu ton exemple :

                        <root> (0)
                    /               \
          <one_pass> (1)           <one_fail> (2)
             /     \                     /     \
    <two_pass>(3) <two_fail>(4) <two_pass>(5) <two_fail>(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

À partir de là, il est facile de trouver des fonctions pour convertir une liste de ['pass', 'fail', 'pass', 'fail'] en un index :

def list_to_number(L):
    acc = 0
    for item in L:
        acc *= 2 #shift number left as we shift in values from the right
        if item == 'fail': #assumes pass == 0 fail == 1
            acc += 1
    return acc


def idx(L): 
    return 2**len(L) - 1 + list_to_number(L)

Exemple complet:

#  Assume we will never have more than 4 events:
#  With 4 events we have 2**4 outcomes.
#  In total there are 2**5-1 possible outcomes including intermediate steps.
#  We will preallocate a list filled with `None` to length 2**5-1 so we have 
#    enough space for all possible outcomes.
tree_data = [None]*(2**5-1)

#insert value 42 given [event_1_pass, event_2_pass, event_3_fail]
tree_data[idx(['pass', 'pass', 'fail'])] = 42

#insert value 56 given [event_1_pass, event_2_pass, event_3_pass, event_4_pass]
tree_data[idx(['pass', 'pass', 'pass', 'pass'])] = 56

#retrieve value given [event_1_pass, event_2_pass, event_3_fail]
print(tree_data[idx(['pass', 'pass', 'fail'])])
# prints: 42

#retrieve value given [event_1_fail, event_2_pass, event_3_fail]
print(tree_data[idx(['fail', 'pass', 'fail'])])
# prints: None because we never stored anything there.
1
Aaron 14 mars 2019 à 18:19