假设我有一个大的二维数组,其值范围在 [0,1] 范围内,其中 0 表示“不可能”,1 表示“极有可能”。
如何根据上述概率在该数组中选择一组随机点?
看待问题的一种方法是(暂时)忽略您正在处理二维网格的事实。你拥有的是一组加权的项目。从这样的集合中随机选择的标准方法是:
- 将权重相加,称为总和
s
- 选择一个统一的随机值
0 <= u < s
- 迭代项目,保持总计
t
您检查过的物品的重量
- 立刻
t >= u
,选择您当前正在查看的项目(您刚刚添加了重量的项目)。
可以通过添加以下步骤进行修改,以进行多项选择而不进行替换:
如果对权重求和不可行或不受欢迎(如果您的数组特别大,则可能是这样),还有其他选择。第一个想到的是拒绝抽样,这是一个相当广泛的主题,所以我只会向您推荐有关该主题的谷歌和维基百科,因为它们的覆盖范围非常好。
编辑:忘记回到你有一个二维数组的事实。您可以通过预先计算(MIPMAP 样式)地图中区域层次结构的权重总和来显着加快速度,这样您就可以快速跳到实际选定权重的位置。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)