在加权随机选择中何时使用替换与非替换？

加权随机选择：替换与非替换

加权随机选择是各种应用中使用的基本技术。它涉及从给定列表中采样元素，概率分布由指定权重确定。当选择具有替换的元素时，每个项目可以被选择多次，从而导致选择具有较高权重的项目的可能性更高。相比之下，无替换选择会在选择项目后限制其选择。

寻找有效的加权随机选择算法（尤其是替换算法）可能具有挑战性。现有方法（包括修改后的储层算法）被证明不适合从小列表大小中选择显着分数。

一种有效的方法：别名方法

在此场景中表现出色的一种方法是别名方法。该技术创建一组结构化的箱，每个箱代表加权列表的一部分。通过利用位操作，可以有效地对容器进行索引，从而避免二进制搜索。每个 bin 包含原始列表中的两个元素，从而能够有效地表示分布。

例如，考虑五个等权重选择的列表：(a:1, b:1, c:1, d: 1、e:1)。别名方法创建一组八个箱，每个箱的概率质量为 0.125。

1. 归一化： 调整权重以使其总和为 1.0。在这种情况下， (a:0.2 b:0.2 c:0.2 d:0.2 e:0.2).
2. 分区： 分配权重低于分区概率 (0.125) 的 bin，从重量最低。这里，(p1{a|null,1.0},p2,p3,p4,p5,p6,p7,p8).
3. 填充：用最高的填充分区中的剩余空间权重变量。例如，(p1{a|null,1.0},p2{a|b,0.6},p3,p4,p5,p6,p7,p8)。

运行时选择：

在运行时，我们生成一个随机数并使用位运算来有效地确定与概率分布相对应的 bin。如果 bin 被分割，我们使用随机数的小数部分在 bin 中的两个元素之间进行选择。

总之，别名方法提供了一种有效的带替换的加权随机选择技术。它利用位操作进行快速 bin 索引，并通过仔细地将权重划分为可管理的 bin 来实现准确的概率分布。

以上是在加权随机选择中何时使用替换与非替换？的详细内容。更多信息请关注PHP中文网其他相关文章！