Python: manipuler des sous-arbres

Question

Je suis un nooby. Je tiens à remercier Allen Downey, Jeffrey Elkner et Chris Meyers et «Comment penser comme un informaticien» pour ce que je sais.

Je crée un programme inspiré de la génétique pour générer des équations qui correspondent à certains problèmes.

La classe de noeud se présente comme suit:

class Node(object): 
    ''' 
    ''' 
    def __init__(self, cargo, left=None, right=None): 
     self.cargo = cargo 
     self.left = left 
     self.right = right 
     self.parent = None 
     self.branch = None 
     self.seq = 0 

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

    def copy(self): 
     return copy.deepcopy(self) 

I ont une classe Tree qui contient un attribut: self.data qui est lié à une série de noeuds formant un arbre qui je peux traverser pour produire une équation.

Pour effectuer un crossover, j'aimerais pouvoir permuter des sous-arbres choisis au hasard à partir de deux instances de Tree.

Lorsque self.data est en cours de construction, il construit un dictionnaire avec une clé séquentielle contenant chaque nœud comme valeur. Un tel dossier ressemble à ceci:

3: <__main__.Node object at 0x0167B6B0>} 

Je pensais que je serais intelligent et vous suffit de choisir un nœud chacun de deux cas d'arbres et échanger leurs parents respectifs node.left ou node.right valeurs. Chaque nœud enregistre s'il est à gauche ou à droite dans son attribut node.branch. Je ne sais pas comment faire référence self.data(subnode) pour le changer.

Et les deux instances d'arbre devraient avoir accès aux nœuds de l'autre par l'adresse enregistrée dans le dictionnaire.

Je crains de devoir copier et remplacer chaque sous-arbre.

Tous les commentaires seraient appréciés.

Merci,

Peter Stewart

Nanaimo, Canada

Answer 1

Si je comprends bien, vous cherchez quelque chose comme ça ...

(je n'ai pas testé.)

def swap_nodes(dict_1, key_1, dict_2, key_2): 
    node_1 = dict_1[key_1] 
    node_2 = dict_2[key_2] 

    # Update dicts and seq fields for the two nodes... 
    dict_1[key_1] = node_2 
    node_2.seq = key_1 
    dict_2[key_2] = node_1 
    node_1.seq = key_2 

    # Update the parents... 
    if node_1.branch == "left": 
     node_1.parent.left = node_2 
    else: 
     node_1.parent.right = node_2 

    if node_2.branch == "left": 
     node_2.parent.left = node_1 
    else: 
     node_2.parent.right = node_1 

    # Now update the branch and parent fields of the nodes... 
    node_1.branch, node_2.branch = node_2.branch, node_1.branch 
    node_1.parent, node_2.parent = node_2.parent, node_1.parent 

Answer 2

Malheureusement, vous ne nous fournissez pas le Tree classe, mais supposons qu'il est quelque chose comme:

class Tree(object): 
    def __init__(self): 
    self.data = None 
    self.nextkey = 0 
    self.thedict = {} 

lorsque de nouveaux nœuds sont insérés

avec les différents attributs étant mis à jour avec précision. Maintenant, alors que vous parlez de "l'adresse enregistrée dans le dictionnaire", il est clair que la valeur du dict n'est PAS "une adresse" - mais plutôt un objet Node (si vous définissez une méthode spéciale dans votre nœud, vous pouvez pour voir cela d'une manière plus claire, ce que vous voyez est la représentation par défaut, utilisée pour tous les objets Python dont le type ne définit pas ou n'hérite pas __repr__). Par conséquent, l'échange de sous-arbres aléatoires entre deux arborescences différentes requiert uniquement la mise à jour de toutes les nombreuses informations redondantes que vous conservez (et qui doit être ALL sync).En passant, il serait plus simple si de telles mises à jour étaient des méthodes de Tree et/ou Node et donc utilisables pour différents types de "edit" (insertion, suppression, etc), plutôt qu'incroyable dans une fonction qui effectue les mises à jour dans le cadre d'un échange aléatoire - c'est une bonne pratique OO. Mais, c'est un peu un problème secondaire. Vous ne nous dites pas exactement comment fonctionne l'attribut branch, je suppose qu'il s'agit d'une chaîne, 'gauche' ou 'droite' selon le cas (ou Aucun s'il n'y a pas de parent, c'est-à-dire un noeud racine).

Pour supprimer une sous-arborescence, vous devez mettre à jour: le nœud parent, en définissant sur None son attribut approprié; la racine du sous-arbre, définissant à None ses attributs parents et branches; AND the Tree, supprimant cette entrée de l'attribut thedict de l'arborescence. Vous devrez également vous souvenir de ce que le parent et la branche étaient afin d'être en mesure d'insérer un autre sous-arbre à cet endroit. Par conséquent ...:

def removeSubtreeFromTree(tree, keyindict): 
    subtreenode = tree.thedict.pop(keyindict) 
    parent, branch = subtreenode.parent, subtreenode.branch 
    # a sanity chech can't hurt...;-) 
    assert getattr(parent, branch) is subtreenode 
    subtreenode.parent, subtreenode.branch = None, None 
    setattr(parent, branch, None) 
    return subtreenode, parent, branch 

Maintenant, pour ajouter un nouveau sous-arbre à un parent et la branche donnée dans un arbre est plus simple:

def addNewSubtree(tree, subtreenode, parent, branch): 
    # sanity checks R us 
    assert getattr(parent, branch) is None 
    assert subtreenode.parent is None 
    assert subtreenode.branch is None 
    setattr(parent, branch, subtreenode) 
    subtreenode.parent = parent 
    subtreenode.branch = branch 
    tree.thedict[tree.nextkey] = subtreenode 
    tree.nextkey += 1 

Remarque vous ne pouvez pas simplement réutiliser les clés précédentes: il pourrait y avoir être un "conflit" (en supposant que les clés ne sont uniques que dans un seul Arbre donné ... si vous les avez rendues uniques globalement à la place, alors vous pourriez en effet les réutiliser).

Enfin, mettre ces deux opérations et un peu plus ensemble peut être fait. Si vous n'avez jamais besoin d '"échanger" la racine même d'un arbre, c'est plus simple (pas de cas particulier pour traiter un sous-arbre sans parent ...) donc je vais supposer que (si vous voulez plus de généralité, vous devrez coder les cas particuliers tatillonnes - idéalement après refactoring choses à des méthodes comme je l'ai déjà suggéré, -) ...:

def randomNonrootSubtree(tree): 
    # we're in trouble if the tree ONLY has a root w/no really SUB trees;-) 
    assert len(tree.thedict) > 1 
    while True: 
     thekey = random.choice(tree.thedict.keys()) 
     subtree = tree.thedict[thekey] 
     if subtree.parent: return thekey 

et enfin ...:

def theSwapper(t1, t2): 
    k1 = randomNonrootSubtree(t1) 
    k2 = randomNonrootSubtree(t2) 
    st1, p1, b1 = removeSubtreeFromTree(t1, k1) 
    st2, p2, b2 = removeSubtreeFromTree(t2, k2) 
    addNewSubtree(t1, st2, p1, b1) 
    addNewSubtree(t2, st1, p2, b2)