选择元素的概率与元素值成比例 [英] Select element from collection with probability proportional to element value

问题描述

我有一个顶点列表，从中我必须选择一个随机顶点，概率与deg（v）成比例，其中deg（v）是一个顶点度。此操作的伪代码如下所示：

 选择u∈L，概率deg（u）/ Sigma∀v∈L deg（v）
  

其中u是随机选择的顶点，L是顶点列表，v是一个顶点在L.问题是，我不明白如何去做。有人可以向我解释，如何得到这个随机顶点。如果有人能向我解释这一点，我将不胜感激。伪代码将更加欣赏;）。

解决方案

最简单的解决方案是填充大小 Sum（d（v）），对于每个 v - 您将 中的 v > d（v）列表中的条目。

现在，选择一个均匀分布的变量 x 范围 [0，Sum（d（v））），并返回 list [x]

这个方法需要 O（n ^ 2）空间（因为对于简单图 Sigma（d（v））是O（n ^ 2）），并且初始化时间也是 O（n ^ 2），但它只做一次。假设你要选择一个顶点很多次，每次你选择它，除了第一个，将会是 O（1） [假设 O（1）随机化函数和随机访问列表]。

I have a list of vertices, from which I have to pick a random vertex with probability proportional to deg(v), where deg(v) is a vertex degree. The pseudo code for this operation look like that:

Select u ∈ L with probability deg(u) / Sigma ∀v∈L deg(v)

Where u is the randomly selected vertex, L is the list of vertices and v is a vertex in L. The problem is that I don't understand how to do it. Can someone explain to me, how to get this random vertex. I would greatly appreciate if someone can explain this to me. Pseudo-code will be even more appreciate ;).

解决方案

Simplest solution is to populate a list of size Sum(d(v)), for each v - you will hold a reference to v in exactly d(v) entries of your list.

Now, select a uniformly distributed variable x in range [0,Sum(d(v))), and return list[x]

This method requires O(n^2) space (since for simple graphs Sigma(d(v)) is O(n^2)), and the initialization time is also O(n^2), but it is done only once. Assuming you are going to chose a vertex a lot of times, each time you select it, except the first, will be O(1) [assuming O(1) randomization function and a random access list].

这篇关于选择元素的概率与元素值成比例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！