加权随机图

Question

假设我有一个大的二维数组，其值范围在 [0,1] 范围内，其中 0 表示“不可能”，1 表示“极有可能”。

如何根据上述概率在该数组中选择一组随机点？

Answer 1

看待问题的一种方法是（暂时）忽略您正在处理二维网格的事实。你拥有的是一组加权的项目。从这样的集合中随机选择的标准方法是：

1. 将权重相加，称为总和s
2. 选择一个统一的随机值0 <= u < s
3. 遍历项目，保留t您检查过的项目的重量总计
4. 一旦t >= u，选择您当前正在查看的项目（您刚刚添加了重量的项目）。

可以通过添加以下步骤进行修改，以进行多项选择而不进行替换：

• 每次选择后，减去所选项目的重量s（如果您的重量是浮点并且稳定性是一个问题，您可能更愿意从头开始重新计算，至少偶尔如此）。

• 从 2 开始重复，但在步骤 3 中跳过先前选择的项目。

如果对权重求和不可行或不受欢迎（如果您的数组特别大，则可能是这样），还有其他选择。第一个想到的是拒绝抽样，这是一个相当广泛的主题，所以我只会向您推荐有关该主题的谷歌和维基百科，因为它们的覆盖范围非常好。

编辑：忘记回到你有一个二维数组的事实。您可以通过预先计算（MIPMAP 样式）地图中区域层次结构的权重总和来显着加快速度，这样您就可以快速跳到实际选定权重的位置。