估计树的大小

我想估计一个大型树结构中的树叶数，我无法详尽地访问每个节点。这个算法是否合适？它有名字吗？另外，如果我不恰当地使用任何条款，请小心。估计树的大小

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)

来源

2010-05-07 Full Decent

我看不出这可能会在任何种类的不平衡树上工作。定制树对象本身以在插入和移除过程中跟踪这种东西会更有意义。 – 2010-05-07 14:52:41

认为巨大，就像所有可能的跳棋游戏的树。不是记忆中的东西。 – 2010-05-07 14:54:44

我明白了。 :)看起来你可能有一个树在物理上存在（即使它是分裂的），或者你有一棵实际上并不存在的树，并根据需要从给定节点生成树。在第一种情况下，树型代码需要保留统计信息以给你想要的东西。第二种情况，你不能解决任何任意的树结构。如果你有特殊的第二种情况 - 比如跳棋游戏排列 - 有比统计抽样更好的方法。 – 2010-05-07 15:01:39

这可能是可能的，如果你可以让你的树一些安全的假设（如：？是平衡）和它的使用（在那里有多少叶子会在同一节点的孩子一个安全的假设？）。如果您每次添加/删除叶节点时都保持运行计数器（计数器），那更好。然后，您只需在一个操作中访问您的计数器变量。

来源

2010-05-07 14:56:31 FrustratedWithFormsDesigner

我不能假设树是平衡的。但我可以在深度上设置一个上限。这有帮助吗？这棵树将是巨大的，例如代表完美信息游戏中的所有动作。 – 2010-05-07 15:18:05

嗯，这可能会给你一个叶片数的最坏情况估计，但要接近，你需要知道更多。有没有办法知道/估计有多少分支实际达到最大深度？ – FrustratedWithFormsDesigner 2010-05-07 15:47:42

我不知道如何估计有多少分支达到最大深度，但这些实际上是我唯一有兴趣计算的分支。我将继续讨论其他问题。 – 2010-05-07 15:52:24

估计树大小的一个理论，基本为指数时间和启发式的某些领域算法，是

手册可满足性的分析，IOS出版社2009年，ISBN 978-1-58603-929 -5 （编辑阿明BIERE，Marijn JH Heule，汉斯·范Maaren和托比沃尔什） http://www.iospress.nl/book/handbook-of-satisfiability/

即第7章 “分支启发式的Fundaments”（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年，估计回溯方案的效率）的方法。

来源

2011-11-05 13:57:07

估计树的大小

回答

相关问题