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

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

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