Comment obtenir un noeud aléatoire d'un arbre?

Question

Cela semble facile, mais j'ai trouvé l'implémentation difficile. J'en ai besoin pour un simple problème de programmation génétique que j'essaie de mettre en œuvre. La fonction devrait, à partir d'un nœud, renvoyer le nœud lui-même ou l'un de ses enfants de sorte que la probabilité de choisir un nœud soit normalement distribuée par rapport à sa profondeur (donc la fonction devrait renvoyer principalement les nœuds intermédiaires). ceux-là - mais ce n'est pas vraiment nécessaire si cela le rend beaucoup plus complexe, si tous les nœuds sont choisis avec une probabilité égale, c'est assez bon).

Merci

Answer 1

Pour le cas uniforme, si vous connaissez la profondeur de chaque nœud, vous pouvez aller à gauche avec la taille de probabilité (à gauche)/taille (ce), à ​​droite avec la taille de probabilité (à droite)/taille (ce), sinon, choisissez le nœud actuel. Un nombre aléatoire unique à chaque moment devrait suffire:

int r = rand() % size(this); 
if (r < size(left)) { /* go left */ } 
else if (r > size(left)) { /* go right */ } 
else { /* pick this node */ } 

En fait, avec quelques ajustements, vous pouvez passer probablement un nombre aléatoire à utiliser à chaque nœud. Après réflexion, oui vous pouvez: si vous allez à gauche, utilisez r non modifié; si vous allez à droite, soustrayez (size(left) - 1) de r.

Pour la distribution normale, il suffit d'utiliser une variable aléatoire normalement distribuée avec une moyenne de la moitié de la profondeur pour choisir à l'avance la profondeur à aller, puis revenir à l'algorithme ci-dessus. Soyez averti que cela se répartira entre les nœuds du milieu en fonction des tailles relatives de leurs sous-arbres, pas uniformément.