我有一个大型有向无环图 (DAG)，我想根据以下标准从中有效地绘制样本节点：
- 我指定了一个永远不能采样的固定节点 A
- 直接或间接引用 A 的节点永远不会被采样
- 所有其他节点都以相同的概率进行采样
节点存储为对象，并带有指向它们引用的其他节点的指针，可以从直接或间接引用其他所有节点的单个根节点到达整个图。
有一个好的算法可以做到这一点吗？理想情况下不需要大量额外内存，因为 DAG 很大！
I have a large directed, acylic graph (DAG) from which I would like to efficiently draw a sample node according to the following criteria:
- I specify a fixed node A that must never be sampled
- Nodes that directly or indirectly refer to A are never sampled
- All other nodes are sampled with equal probability
Nodes are stored as objects with pointers to the other nodes that they refer to, the entire graph can be reached from a single root node that refers to everything else directly or indirectly.
Is there a good algorithm to do this? Ideally without requiring large amounts of additional memory since the DAG is large!
发布评论
评论（2）
我能想到的唯一解决方案是将
（使用广度优先遍历从根开始遍历它们），O(|E|+|V|)
从节点 A 开始，通过向后遍历边来删除所有前驱
（同样 O(|E|+|V|)）
从剩余节点中选择一个随机节点。
这将导致 O(|E|+|V|) 算法和 O(|V|) 内存需求。
请注意，您不必复制步骤 1 中的节点，只需保存对该节点的引用。
The only solution I can come up with is to
put the nodes in a hash set
(traverse them from the root using, say, a breadth first traversal), O(|E|+|V|)
start from node A and remove all predecessors by traversing the edges backwards
(again O(|E|+|V|))
select a random node from the remaining nodes.
This would result in a O(|E|+|V|) algorithm with a O(|V|) memory requirement.
Note that you wouldn't have to copy the nodes in step 1, only save a reference to the node.
无论如何，我不是这个领域的专家，但我认为您可能需要一个蒙特卡洛马尔可夫链抽样方法，例如Metropolis-Hastings 或 吉布斯采样 算法。
您可以在线找到一些代码示例，并且您可能必须修改代码才能完全执行您想要的操作。关于这个主题有一些很好的演示，例如这个< /a>.
一些可能对您有所帮助的软件是：
我不知道你对图论的熟悉程度，所以我不确定这对你来说有多困难来实施这一点。
希望这有帮助...
I'm not an expert in this area by any means, but I think you may want a Monte Carlo Markov chain sampling method such as the Metropolis-Hastings or Gibbs sampling algorithm.
You can find some code samples online, and you might have to modify the code to do exactly what you want it to do. There's some good presentations on the topic, like this.
Some software that might help you along are:
I don't know your familiarity with graph theory, so I'm not sure how difficult it would be for you to implement this.
Hope this was helpful...