如何进行有替换和无替换的有效加权随机选择？

带替换和不带替换的加权随机选择

为了应对编程挑战，我们寻求从列表中进行加权随机选择的有效算法，有替换和无替换。

带替换的加权选择

带替换的加权选择的一种有效方法是别名方法。该技术为每个加权元素创建一组相同大小的箱。通过利用位操作，我们可以有效地索引这些容器，而无需诉诸二分搜索。每个 bin 存储一个百分比，表示原始加权元素之间的边界。

考虑具有相等权重的五个元素的示例：(a, b, c, d, e)。

别名方法实现

1. 归一化权重：将每个权重除以总和，使其总和为 1.0。
2. 确定大于或等于该数字的最小 2 次幂元素（此处为 8）。
3. 为每个元素分配一个空分区。

4. 重复以下步骤，直到分配所有权重：

   • 将尽可能多的剩余重量最小的元素放入空分区中。
   • 如果分区未填满，则添加剩余最重的元素。

对于我们的示例，经过几次迭代后，我们有以下分区：

• p1: {a, 1.0}
• p2: {a, b, 0.6}

运行时选择

1. 生成 0 到 1 之间的随机数。
2. 对随机数进行位移以查找分区索引。
3. 如果分区被分割，则使用移位数的小数部分来决定返回哪个元素。

加权选择而不替换

而算法就像加权水库方法存在用于无替换的非加权选择一样，这个问题仍然没有解决。

以上是如何进行有替换和无替换的有效加权随机选择？的详细内容。更多信息请关注PHP中文网其他相关文章！