1

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

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

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

例如，选择权重较低的元素 A 或 B 的可能性（30%）高于算法选择元素 CE（10%）或 D（20%）的可能性

4

1 回答 1

2

正如@Dukeling 所说，我们需要更多信息。就像您如何解释和使用选择机会一样。

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

假设你从badness score开始

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

目标是计算适合度/选择分数S[i]，我假设您将以轮盘赌的方式使用它。

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

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)。 正如您在这个问题中已经看到的那样，二分搜索可用于快速查找哪个项目拥有中奖彩票。二分查找需要查找的是ticket 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 个单位的 badness 会导致选择机会的不同差异。

于 2013-05-25T17:07:41.563 回答