Оценивая размер дерева

Question

Я бы хотел оценить количество листьев в большой древовидной структуре, для которых я не могу исчерпывающе посетить каждый узел. Этот алгоритм подходит? У него есть имя? Также, пожалуйста, педантируйте, если я неправильно использую какие-либо термины.

sum_trials = 0
num_trials = 0
WHILE time_is_not_up
    bits = 0
    ptr = tree.root
    WHILE count(ptr.children) > 0
         bits += log2(count(ptr.children))
         ptr = ptr.children[rand()%count(ptr.children)]
    sum_trials += bits
    num_trials++
estimated_tree_size = 2^(sum_trials/num_trials)

Answer 1

Это может быть возможно, если вы можете сделать некоторые безопасные предположения о вашем дереве (например: сбалансировано ли оно?) И его использовании (есть ли безопасное предположение о том, сколько листьев будет дочерними для одного и того же узла?). Еще лучше, если вы будете поддерживать счетчик (счетчик) при каждом добавлении / удалении конечного узла. Затем вы просто получаете доступ к переменной счетчика за одну операцию.

Answer 2

Теория оценки размеров деревьев, фундаментальная для анализа экспоненциального времени алгоритмы и для определенных областей эвристики, в

Справочник по удовлетворенности, IOS Press 2009, ISBN 978-1-58603-929-5 (редакторы Armin Biere, Marijn J.H. Heule, Ханс ван Маарен и Тоби Уолш) http://www.iospress.nl/book/handbook-of-satisfiability/

а именно глава 7 «Основы ветвящей эвристики» (стр. 205-244). Основной технический отчет http://www.swan.ac.uk/compsci/research/reports/2008/CSR7-2008.pdf Глава доступна на http://www.booksonline.iospress.nl/Content/View.aspx?piid=11712

Эта теория обобщает подход в вышеупомянутой работе Дональда Кнута (1975, Оценка эффективности программ возврата).