加权随机地图 [英] Weighted random map

问题描述

假设我有值的大的二维数组在区间[0,1]，其中0表示不可能，1表示非常有可能。

Suppose I have a big 2D array of values in the range [0,1] where 0 means "impossible" and 1 means "highly probable".

我怎么能在这个数组中选择根据上述概率随机点集的？

How can I select a random set of points in this array according to the probabilities described above ?

推荐答案

一看这个问题的方法就是忽略（暂时），您正在处理一个2D网格的事实。你所拥有的是一组权重的物品。从这样一组随机选择的标准方法是：

One way to look at the problem is to ignore (for the moment) the fact that you're dealing with a 2d grid. What you have are a set of weighted items. A standard way of randomly selecting from such a set is to:

1. 和的权重，叫的总和取值
2. 选择一个统一的随机值 0℃= U＆LT;小号
3. 遍历项目，保留的项目权重的总运行 T 您已经检查
4. 尽快 T＆GT;。= U ，选择您目前正在观察（：一个刚刚添加的重量）的项目

1. sum the weights, call the sum s
2. select a uniform random value 0 <= u < s
3. iterate through the items, keeping a running total t of the weights of the items you've examined
4. as soon as t >= u, select the item you're currently looking at (the one whose weight you just added).

这可以被修改，以进行多项选择，无需更换中加入以下步骤：

This can be modified to make multiple selections without replacement by adding the following steps:

• 每个选择后，从扣除所选项目的重量的S- （如果你的权重浮点和稳定性是一个问题，你可能preFER从零开始重新计算，至少偶尔）。

• After each selection, deduct the weight of the selected item from s (if your weights are floating point and stability is an issue, you might prefer to recalculate it from scratch, at least occasionally).

2的重复，但在第3步跳跃项已pviously选择$ P $。

repeat from 2, but in step 3 skip items that have been previously selected.

如果总结的权重是不可行或不希望（它可能是，如果你的阵列是特别大），还有其他选择。第一个想到的就是拒绝抽样，这是一个相当宽泛的主题所以我就请您看看谷歌和维基百科上的那一个，因为其覆盖面是pretty的好。

If summing the weights is infeasible or undesirable (which it may be if your array is particularly large) there are other options. The first that comes to mind is rejection sampling, which is a fairly broad topic so I'll just refer you to google and wikipedia on that one, as their coverage is pretty good.

编辑：忘了回来，你有一个二维数组的事实。您可以通过pre计算（MIPMAP式）显著加快速度区域在地图上一个层次的权重的总和，因此您可以快速跳转到实际的选择权重的位置。

Forgot to come back to the fact that you have a 2D array. You can speed things up significantly by pre-computing (MIPMAP-style) the sums of weights of a hierarchy of regions in the map, so you can skip quickly to the location of the actual selected weight.

这篇关于加权随机地图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！