加权随机图

Question

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

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

Answer 1

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

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

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

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

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

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

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

Answer 2

代码：

  count = 0
  maxPointsInSet = 100
  foreach(point in array){
      if(randomWithChacnce(point.value))) {
         addToSet(point)
         count++
      }
      if(count == maxPointsInSet)
         break;
  }

  function randomWithChacnce(int num){
    random = a randomized number between 0 to 1 // or random from 1 to 100 num*100
    if(num >= random)
     return true;
    return false
  }

如果您需要任何特定语言的版本，请询问我