估算一棵树的大小

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)

- William Entriken

---

我不明白这个在任何不平衡的树上都可能起作用。更有意义的做法是自定义树对象，在插入和删除期间跟踪此类信息。 - Clinton Pierce

想象巨大，就像一个包含所有可能的跳棋游戏的树。不是存储在内存中的东西。 - William Entriken

我理解很好。 :) 看起来你可以有一个实际存在的树（即使它被分割了），或者你可以有一个并不存在的树，需要从给定节点生成。在第一种情况下，生成树的代码需要保持统计数据以提供所需内容。在第二种情况下，您无法解决任何任意树形结构。如果您有特殊的第二种情况 - 如跳棋游戏排列 - 有比统计抽样更好的方法可用。 - Clinton Pierce

这里是我可以阅读的一些更多文档： 估计搜索树大小，Philip Kilby等人 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.129.5569&rep=rep1&type=pdf Knuth, D. 1975年。估计回溯程序的效率。 计算数学29（129）：121-136。 - William Entriken

如果你的估计要作为统计量有意义，你还需要计算（或估计）方差。 - President James K. Polk

Answer 1

如果您可以对树进行一些安全的假设(例如：它是否平衡？)并且了解其使用情况(同一节点的叶子节点数量是否有安全的假设？)，那么这可能是可行的。更好的方法是，每次添加/删除叶子节点时都维护一个运行计数器(counter)。然后，您只需在单个操作中访问计数器变量。

- FrustratedWithFormsDesigner

---

我不能假设树是平衡的。但我可以对深度设定一个上限。这有帮助吗？例如，这棵树将会非常庞大，代表了完全信息游戏中的所有移动。 - William Entriken

哦，那可能会为您提供叶子节点数量的最坏估计，但要更接近，您需要了解更多信息。是否有一种方法可以知道/估计实际达到最大深度的分支数？ - FrustratedWithFormsDesigner

我不知道如何估计有多少分支达到最大深度，但这些实际上是我感兴趣的唯一分支。我将继续提出其他问题来讨论这个主题。 - William Entriken

Answer 2

一种估算树大小的理论，对于分析指数时间算法和某些启发式领域至关重要，收录在《可满足性手册》中，IOS Press 2009年版，ISBN 978-1-58603-929-5（编辑Armin Biere、Marijn J.H. Heule、Hans van Maaren和Toby Walsh），其中第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获取。

这个理论推广了 Donald Knuth 在1975年的论文中提出的方法，该论文是关于回溯程序效率估算的。

- Oliver Kullmann