在边缘遍历昂贵的树中统计估计总节点

我有一棵定向树，我想要它的大小。 我没有关于它的深度或节点分布的信息。 有两个主要障碍：

1）树很大（〜十亿个节点）

2）边缘遍历是昂贵的。

是否有统计方法可以用来快速估算其大小（节点数量）并确定有界误差？ 不幸的是，Google搜索只会导致精确计数算法，在这些限制条件下执行效果不佳。

奖金

如果我放松从树到DAG（有向无环图）的约束，我可以同时获得其大小和数量的唯一路径吗？ 例如，对于这个DAG（每条边都指向下方）

有19个节点（大小）和23个路径（4个额外的路径，因为红色边缘为其目的地节点提供了1个路径，而另外3个路径指向了其目的地节点的子节点）

我试过的东西

对于树木案例，我正在想的是：

amounts = []
def estimateHelper(node):
    amounts[node.depth].push(len(node.children))
    for each child in small random sample of node.children:
        estimateHelper(child)
def estimate(root):
    estimateHelper(root)
    reach = 0
    for (j = len(amounts) - 1; j >= 0; --j):
        avgChildrenPerNodeAtThisLevel = avg(amounts[j])
        reach = avgChildrenPerNodeAtThisLevel + avgChildrenPerNodeAtThisLevel * reach
    return reach

它基本上计算树的最深节点处的“范围”，然后将其传播回到上面的级别以找到该级别的范围。 它会这样做直到它最终找到树根的“伸手可及的距离”。 我不确定是否在上述算法中对节点的均匀分布做出任何假设。 重申一下，我不知道给定树会有什么样的分布。

假设它可行，这也解决了DAG的“路径”。 一旦你拥有了所有的“路径”，我正在考虑使用生日悖论的逆来找出有多少个独特的节点。 生日悖论的答案是“我们需要选择多少天（路径），直到我们在一年365个独一无二的日子里以一定的概率重复一天”。 所以我们不断尝试随机路径（天），直到我们碰到一个重复的节点，我们重复几次以找到该事件的概率，然后将其插入生日悖论中以找到唯一节点的数量（年）。 请注意，生日悖论也假设了一致性。

没有一个是非常严格的。 最理想的是给我一个误差界限的估计值，以及一个足够严格地描述算法的论文。 任何正确的方向指针非常赞赏。

---

Knuth在回溯树搜索的背景下为此撰写了一篇论文：估算回溯计划的效率 - 例如http://www.ams.org/journals/mcom/1975-29-129/S0025-5718-1975-0373371- 6 / S0025-5718-1975-0373371-6.pdf。 搜索术语Knuth树估计还可以找到引用该文件的论文，例如ftp://ftp.cs.indiana.edu/pub/techreports/TR60.pdf和http://www.cs.ubc.ca/~hutter/EARG.shtml /earg/stack/WS06-11-005.pdf。

我不知道这将如何转化为一般的DAG，但是 - 同样在树搜索的情况下 - 您可以通过添加约束条件来重新定义DAG为具有相同顶点数的树，这些约束条件禁止在第一个点之后进入每个顶点的边。 例如，当逐个选择数字的一个子集时，要求按照升序列出 - 然后（1,3,8）只有单一的祖先（1,3）。

想想看，您还可以定义一棵树，其中每条DAG路径的边界定义了树中的不同边界。 计算此处的边数可能会告诉您有关DAG路径数的信息。

链接地址: http://www.djcxy.com/p/65291.html

上一篇: Statistic estimation of total nodes in a tree where edge traversal is expensive

下一篇: How to measure fractal dimension of surf figure in matlab