2

我有一个大的有向无环图（DAG），我想根据以下标准有效地从中绘制一个样本节点：

  1. 我指定了一个永远不能被采样的固定节点 A
  2. 直接或间接引用 A 的节点永远不会被采样
  3. 所有其他节点以相等的概率进行采样

节点存储为带有指向它们所引用的其他节点的指针的对象，整个图可以从直接或间接引用其他所有内容的单个根节点到达。

有没有一个好的算法来做到这一点？理想情况下不需要大量额外内存，因为 DAG 很大！

4

2 回答 2

2

我能想出的唯一解决方案是

  1. 将节点放入哈希集中
    （使用广度优先遍历从根开始遍历它们），O(|E|+|V|)

  2. 从节点 A 开始并通过向后遍历边删除所有前任
    （再次 O(|E|+|V|)）

  3. 从剩余节点中选择一个随机节点。

这将导致 O(|E|+|V|) 算法具有 O(|V|) 内存要求。

请注意，您不必在步骤 1 中复制节点，只需保存对节点的引用。

于 2010-08-19T14:53:04.717 回答
0

无论如何，我都不是该领域的专家，但我认为您可能需要蒙特卡洛马尔可夫链采样方法，例如Metropolis-Hastings或Gibbs 采样算法。

您可以在线找到一些代码示例，并且您可能必须修改代码才能完全按照您的意愿进行操作。有一些关于这个主题的很好的演讲，就像这样。

一些可能对您有所帮助的软件是：

我不知道你对图论的熟悉程度，所以我不确定你实现它会有多困难。

希望这有帮助...

于 2010-08-19T14:22:40.667 回答