木からランダムなノードを取得する方法？

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 */ }

実際には、いくつかの調整で、あなたはおそらく、すべてのノードで使用する1回の乱数ダウンを渡すことができます。いくつかの考えた後、はい、できます：あなたが左に行けば、使用が変更されていないr。あなたが右に行く場合、(size(left) - 1)から減算rます。

は、正規分布の場合、どれだけ深く行くことを事前に選択する半分の深さの平均値で正規分布確率変数を使用して、再び上記のアルゴリズムに落ちます。これがない均一、そのサブツリーの相対的なサイズに従って中央のノード間で配布されますので注意してます。