Как получить случайный узел из дерева?

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 неизмененной; если вы идете направо, вычтите (size(left) - 1) от r,

Для нормального распределения просто используйте нормально распределенную случайную величину со средним значением половины глубины, чтобы заранее выбрать глубину, а затем вернуться к приведенному выше алгоритму. Имейте в виду, что это будет распределяться среди средних узлов в соответствии с относительными размерами их поддеревьев, а не равномерно.