C++ 倒置加权随机播放

Question

我有一个加权对象列表，即:

A->1 B->1 C->3 D->2 E->3

C++ 中是否有一种有效的算法可以根据权重选择随机元素？

例如，选择权重较低的元素 A 或 B 的可能性(30%)高于算法选择元素 C E(10%)或 D(20%)的可能性

Answer 1

正如@Dukeling 所说，我们需要更多信息。喜欢你如何解释和使用选择机会。

至少在进化算法领域，适应度缩放(或选择机会缩放)是一个相当大的话题。

假设您从坏分数开始

B[i] = how badly you don't want to select the i-th item

目标是计算适应度/选择分数S[i]，我假设您将在roulette wheel 中使用它时尚。

如您所说，一种明显的方法是使用乘法逆:

S[i] = 1 / B[i]

但是，这可能会有一点问题。 B[i] 中具有低值的相同数量的更改比 B[i] 已经具有高值时的相同数量的更改具有更大的影响。

问问自己:

Say
B[1] = 1     ->     S[1] = 1
B[2] = 2     ->     S[2] = 0.5
So item 1 is twice times as likely to be selected compared to item 2

But with the same amount of change
B[3] = 1000  ->     S[3] = 0.001
B[4] = 1001  ->     S[4] = 0.000999001
Item 3 is only 1.001 times as likely to be selected compared to item 4

我现在只在这里提出一个可能的替代方案。

S[i] = max(B) - B[i] + 1

+ 1 部分有帮助，因此没有项目被选中的机会为零。

计算选择分数的部分到此结束。

---

接下来，让我们来了解一下如何在轮盘时尚中使用选择分数。 假设我们决定使用加法逆方案。

B[1] = 1     ->     S[1] = 1001
B[2] = 2     ->     S[2] = 1000
B[3] = 1000  ->     S[3] = 2
B[4] = 1001  ->     S[4] = 1

然后想象得分中的每个点都对应一张彩票。 让我们为工单分配一个运行 ID。

| Item | Score = #ticket |   ticket ID  |         win chance       |
|   1  |      1001       | 0    to 1000 |  1001/2004 ~ 0.499500998 |
|   2  |      1000       | 1001 to 2000 |  1000/2004 ~ 0.499001996 |
|   3  |         2       | 2001 to 2002 |     2/2004 ~ 0.000998004 |
|   4  |         1       | 2003 to 2003 |     1/2004 ~ 0.000499002 |

总共有2004张票。

要进行选择，请随机选择中奖彩票 ID，即随机范围为 [0,2004)。 二进制搜索 可用于快速查找哪个项目拥有中奖彩票，正如您在 this question 中看到的那样。 .使用二分查找需要查找的是工单 ID 的 边界 值，即 1001,2001,2003 而不是分数本身。

---

为了比较，这里是使用乘法逆方案时的选择机会。

| Item |                    win chance         |
|   1  |           1/1.501999001 ~ 0.665779404 |
|   2  |         0.5/1.501999001 ~ 0.332889702 |
|   3  |       0.001/1.501999001 ~ 0.000665779 |
|   4  | 0.000999001/1.501999001 ~ 0.000665114 |

您可以注意到，在加法逆向方案中，1 个坏度单位始终对应于大约 0.0005 的选择机会差异。

而在乘法逆方案中，1 个单位的坏度会导致选择机会的变化差异。