如何从树中获取随机节点？

Question

看起来很容易，但我发现实施棘手。我想要一个简单的遗传编程问题，我试图实现。给定一个节点，该函数应该返回节点本身或其任何子节点，使得选择一个节点的概率相对于它的深度是正态分布的（所以函数应该主要返回中间节点，但有时根本身或最低 - 但如果这使得它显得更加复杂，如果所有节点都以相同的概率被选中，那就没有必要）。

感谢

Answer 1

对于均匀的情况下，如果你知道每个节点的深度，你可以去左边的概率大小（左）/大小（这一点），右侧的概率大小（右）/大小（这一点），否则选择当前节点。在每一个关键时刻单一的随机数应该足够了：

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

事实上，随着一些调整，你也许可以通过一个随机数下来每个节点使用。经过一番思考，是的，您可以：如果您离开，请使用未修改的r;如果你走对了，从r减去(size(left) - 1)。

对于正态分布，只需使用均值为一半深度的正态分布的随机变量事先选择多深，然后回退到上述算法。被警告，这将根据它们的子树的相对大小在中间节点之间分布，而不是统一的。